Computers and Intractability: A Guide to the Theory of NP-Completeness

Computers and Intractability: A Guide to the Theory of NP-Completeness
Computers and Intractability: A Guide to the Theory of NP-Completeness  
Garey-johnson-79-cover.jpg
Author(s) Michael R. Garey and David S. Johnson
Country USA
Language English
Series A Series of Books in the Mathematical Sciences (Victor Klee, ed.)
Subject(s) Computer science
Genre(s) Textbook
Publisher W. H. Freeman and Company
Publication date 1979
Media type Print
Pages x+338
ISBN 0-7167-1045-5
OCLC Number 247570676
Dewey Decimal 519.4
LC Classification QA76.6 .G35

In computer science, more specifically computational complexity theory, Computers and Intractability: A Guide to the Theory of NP-Completeness is an influential textbook by Michael Garey and David S. Johnson.[1] It was the first book on the theory of NP-completeness and computational intractability.[2] The book features an appendix providing a thorough compendium of NP-complete problems (which was updated in later printings of the book). The book is now outdated in some respects as it does not cover more recent development such as the PCP theorem. It is nevertheless still in print and is regarded as a classic: in a 2006 study, the CiteSeer search engine listed the book as the most cited reference in computer science literature.[3]

Reception

Soon after it appeared, the book received positive reviews by reputed researchers in the area of theoretical computer science.

In his review, Ronald V. Book recommends the book to "anyone who wishes to learn about the subject of NP-completeness", and he explicitly mentions the "extremely useful" appendix with its over 300 NP-hard computational problems. He concludes: "Computer science needs more books like this one.".[4]

Harry R. Lewis praises the mathematical prose of the authors: "Garey and Johnson's book is a thorough, clear, and practical exposition of NP-completeness. In many respects it is hard to imagine a better treatment of the subject." Also, he considers the appendix as "unique" and "as a starting point in attempts to show new problems to be NP-complete".[5]

Twenty-three years after the book appeared, Lance Fortnow, editor-in-chief of the scientific journal Transactions on Computational Theory, states: "I consider Garey and Johnson the single most important book on my office bookshelf. Every computer scientist should have this book on their shelves as well. [...] Garey and Johnson has the best introduction to computational complexity I have ever seen." [6]

References

  1. ^ Garey, M. R.; Johnson, D. S. (1979). Victor Klee. ed. Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. W. H. Freeman and Co.. pp. x+338. ISBN 0-7167-1045-5. MR519066. 
  2. ^ Juris Hartmanis (1982). "Computers and Intractability: A Guide to the Theory of NP-Completeness, book review". SIAM Review 24 (1): 90–91. doi:10.1137/1024022. JSTOR 2029450. 
  3. ^ "Most cited articles in Computer Science - September 2006 (CiteSeer.Continuity)". http://citeseer.ist.psu.edu/articles.html. Retrieved 2007-11-03. 
  4. ^ Ronald V. Book. Review: Computers and intractability: A guide to the theory of NP-completeness Bull. Amer. Math. Soc. (N.S.), 3(2), pp. 898–904, 1980
  5. ^ Harry R. Lewis, Review: Computers and intractability: A guide to the theory of NP-completeness, The Journal of Symbolic Logic, Vol. 48(2), pp. 498–500, 1983
  6. ^ Lance Fortnow, Great Books: Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael R. Garey and David S. Johnson. Computational complexity blog, August 30, 2002.

See also



Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Computers and Intractability: A Guide to the Theory of NP-Completeness — Autor Michael Garey y David S. Johnson Género Libro de texto Tema(s) Ciencias de la comput …   Wikipedia Español

  • Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… …   Wikipedia

  • Intersection number (graph theory) — In the mathematical field of graph theory, the intersection number of a graph is the smallest number of elements in a representation of G as an intersection graph of finite sets. Equivalently, it is the smallest number of cliques needed to cover… …   Wikipedia

  • Matching (graph theory) — In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices. Covering packing dualities… …   Wikipedia

  • Metric dimension (graph theory) — In graph theory, the metric dimension of a graph G is the minimum number of vertices in a subset S of G such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP …   Wikipedia

  • Cut (graph theory) — In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. The cut set of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are… …   Wikipedia

  • Post correspondence problem — The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946.[1] Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability. Contents 1… …   Wikipedia

  • True quantified Boolean formula — The language TQBF is a formal language in computer science that contains True Quantified Boolean Formulas. A fully quantified boolean formula is a formula in first order logic where every variable is quantified (or bound), using either… …   Wikipedia

  • Travelling salesman problem — The travelling salesman problem (TSP) is an NP hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest… …   Wikipedia

  • 3-partition problem — The 3 partition problem is an NP complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. More precisely, given a multiset S of n = 3 m… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”