Description |
x, 338 pages : illustrations ; 24 cm |
Series |
Series of books in the mathematical sciences |
|
Series of books in the mathematical sciences.
|
Contents |
1. Computers, complexity, and intractability -- 2. The theory of NP-completeness -- 3. Proving NP-completeness results -- 4. Using NP-completeness to analyze problems -- 5. NP-hardness -- 6. Coping with NP-complete problems -- 7. Beyond NP-completeness -- Appendix: A list of NP-complete problems |
Summary |
"Shows how to recognize NP-complete problems and offers proactical suggestions for dealing with them effectively. The book covers the basic theory of NP-completeness, provides an overview of alternative directions for further research, and contains and extensive list of NP-complete and NP-hard problems, with more than 300 main entries and several times as many results in total. [This book] is suitable as a supplement to courses in algorithm design, computational complexity, operations research, or combinatorial mathematics, and as a text for seminars on approximation algorithms or computational complexity. It provides not only a valuable source of information for students but also an essential reference work for professionals in computer science"--Back cover |
Analysis |
Computational complexity |
|
Computer algorithms |
|
Computer programming |
Notes |
Includes indexes |
Bibliography |
Includes bibliographical references (pages 291-325) |
Subject |
Algorithms.
|
|
Computational complexity.
|
|
Computer programming.
|
|
Algorithms.
|
|
Computational complexity.
|
|
Computer algorithms.
|
|
Computer programming.
|
Author |
Johnson, David S., 1945- author
|
LC no. |
78012361 |
ISBN |
0716710447 |
|
0716710455 (paperback) |
|
9780716710448 |
|
9780716710455 |
|