Computers and Intractability: A Guide to the Theory of NP-Completeness
From Wikipedia, the free encyclopedia
(Redirected from Computers and Intractability)
| Computers and Intractability: A Guide to the Theory of NP-Completeness | |
|
|
| Author | Michael Garey and David S. Johnson |
|---|---|
| Country | USA |
| Language | English |
| Subject(s) | Computer science |
| Genre(s) | Textbook |
| Publisher | W.H. Freeman and Company |
| Publication date | 1979 |
| Media type | |
| ISBN | 0-7167-1045-5 |
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. It was the very first book on the theory of NP-completeness and computational intractability.[1] 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. [2]
[edit] References
- ^ Juris Hartmanis (1982). "Computers and Intractability: A Guide to the Theory of NP-Completeness, book review". SIAM Review: 90–91. http://www.jstor.org/stable/2029450. Retrieved on 2008-07-03.
- ^ "Most cited articles in Computer Science - September 2006 (CiteSeer.Continuity)". http://citeseer.ist.psu.edu/articles.html. Retrieved on 2007-11-03.
  |
This article about a computer book or series of books is a stub. You can help Wikipedia by expanding it. |
