1979 classic textbook on computational complexity theory
Computers and Intractability: A Guide to the Theory of NP-Completeness
Author
Michael R. Garey and David S. Johnson
Language
English
Series
A Series of Books in the Mathematical Sciences
Subject
Computer science
Genre
Textbook
Publisher
W. H. Freeman and Company
Publication date
1979
Publication place
United States
Media type
Print
Pages
x+338
ISBN
0-7167-1045-5
OCLC
247570676
Dewey Decimal
519.4
LC Class
QA76.6 .G35
Computers and Intractability: A Guide to the Theory of NP-Completeness is a textbook by Michael Garey and David S. Johnson.[1]
It was the first book exclusively 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]
^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. San Francisco, Calif.: W. H. Freeman and Co. ISBN 0-7167-1045-5. MR 0519066. 338 pages. Copy at archive.org
^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.
^"Most cited articles in Computer Science - September 2006 (CiteSeer.Continuity)". Retrieved 2007-11-03.
and 21 Related for: Computers and Intractability information
ComputersandIntractability: A Guide to the Theory of NP-Completeness is a textbook by Michael Garey and David S. Johnson. It was the first book exclusively...
ISBN 978-0-471-34506-0 Garey, Michael R.; Johnson, David S. (1979). ComputersandIntractability: A Guide to the Theory of NP-Completeness. Series of Books in...
computer science researcher, and co-author (with David S. Johnson) of ComputersandIntractability: A Guide to the Theory of NP-completeness. He and Johnson...
problem in the academic theoretical computer science book by M. R. Garey and D. S. Johnson, ComputersandIntractability: A Guide to the Theory of NP-Completeness...
Probabilistic Turing machine Garey, Michael R.; David S. Johnson (1979). ComputersandIntractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0-7167-1045-5...
(2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7. Michael R. Garey and David S. Johnson (1979). ComputersandIntractability: A Guide to the Theory...
David S. (1979), "[GT24] Balanced complete bipartite subgraph", ComputersandIntractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, p. 196...
hdl:10338.dmlcz/103883. Sources Michael R. Garey and David S. Johnson (1979). ComputersandIntractability: A Guide to the Theory of NP-Completeness. W.H...
doi:10.1090/S0002-9947-1965-0170805-7. Michael Garey, and David S. Johnson: ComputersandIntractability: A Guide to the Theory of NP-Completeness. New York:...
ISSN 0167-5060 Garey, Michael R.; Johnson, David S. (1979). ComputersandIntractability: A Guide to the Theory of NP-Completeness. Series of Books in...
discusses the state of the art for the open problems from the book ComputersandIntractabilityand previous columns, in particular, for Graph Isomorphism.) Torán...
1137/S0097539700380754, MR 1954859 Garey, Michael R.; Johnson, David S. (1979). ComputersandIntractability: A Guide to the Theory of NP-Completeness. Series of Books in...
ComputersandIntractability; A Guide to the Theory of NP-Completeness. pp. 96–105. ISBN 978-0-7167-1045-5. Goodrich, Michael. "More NP complete and NP...
Cover". MathWorld. Garey, Michael R.; Johnson, David S. (1979), ComputersandIntractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5...
supplied as part of the input. Garey, M. R.; Johnson, D. S. (1979), ComputersandIntractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, GT4...
in the standard reference, ComputersandIntractability: A Guide to the Theory of NP-Completeness by Michael R. Garey and David S. Johnson. One-in-three...
1016/0012-365X(73)90108-8. Garey, Michael R.; Johnson, David S. (1979). ComputersandIntractability: A Guide to the Theory of NP-Completeness. Series of Books in...
ISBN 978-0-262-03293-3. Garey, Michael R.; Johnson, David S. (1979). ComputersandIntractability: A Guide to the Theory of NP-Completeness. Series of Books in...
proportionality is not known precisely. Michael R. Garey and David S. Johnson (1979), ComputersandIntractability: A Guide to the Theory of NP-Completeness, W.H...
Global Information