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. The book features an appendix providing a thorough compendium of NP-complete problems (which was updated in later printings of the book).

PropertyValue
dbpedia-owl:Book/isbn
  • 0-7167-1045-5
dbpedia-owl:Book/subject
dbpedia-owl:Work/author
dbpedia-owl:Work/genre
dbpedia-owl:Work/language
dbpedia-owl:Work/publishDate
  • 1979-01-01 00:00:00 (xsd:date)
dbpedia-owl:Work/publisher
dbpedia-owl:author
dbpedia-owl:genre
dbpedia-owl:isbn
  • 0-7167-1045-5
dbpedia-owl:language
dbpedia-owl:publishDate
  • 1979-01-01 00:00:00 (xsd:date)
dbpedia-owl:publisher
dbpedia-owl:subject
dbpedia-owl:thumbnail
dbpprop:abstract
  • 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. 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.
dbpprop:author
dbpprop:country
  • USA
dbpprop:genre
dbpprop:hasPhotoCollection
dbpprop:isbn
  • 0-7167-1045-5
dbpprop:language
dbpprop:mediaType
  • Print
dbpprop:name
  • Computers and Intractability: A Guide to the Theory of NP-Completeness
dbpprop:pubDate
  • 1979 (xsd:integer)
dbpprop:publisher
dbpprop:reference
dbpprop:subject
dbpprop:wikiPageUsesTemplate
rdf:type
rdfs:comment
  • 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. The book features an appendix providing a thorough compendium of NP-complete problems (which was updated in later printings of the book).
rdfs:label
  • Computers and Intractability: A Guide to the Theory of NP-Completeness
owl:sameAs
skos:subject
foaf:depiction
foaf:name
  • Computers and Intractability: A Guide to the Theory of NP-Completeness
foaf:page
is dbpprop:redirect of