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

URI: https://gptkb.org/entity/Computers_and_Intractability%3A_A_Guide_to_the_Theory_of_NP-Completeness
GPTKB entity
Statements (51)
Predicate Object
gptkbp:instance_of gptkb:book
gptkbp:author gptkb:Michael_R._Garey
gptkb:David_S._Johnson
gptkbp:field theoretical computer science
gptkbp:first_edition first edition
gptkbp:focus gptkb:NP-completeness
gptkbp:impact influential in computer science
gptkbp:isbn 978-0-387-97565-5
gptkbp:language English
gptkbp:notable_feature gptkb:P_vs_NP_problem
gptkb:Cook's_theorem
computational complexity theory
algorithm design
combinatorial optimization
reduction
graph theory
traveling salesman problem
Turing machines
Hamiltonian path problem
randomized algorithms
graph coloring problem
theory of computation
algorithmic complexity
complexity classes
computational models
decision problems
deterministic algorithms
knapsack problem
computational problems
NP-hardness
approximation algorithms
computational intractability
exponential time
non-deterministic polynomial time
polynomial time
boolean algebra
complexity hierarchy
NP-completeness proof
clique problem
decision tree
satisfiability problem
set cover problem
subset sum problem
vertex cover problem
gptkbp:page_count 340
gptkbp:published_year gptkb:1979
gptkbp:publisher gptkb:W._H._Freeman_and_Company
gptkbp:subject gptkb:computer_science
complexity theory
gptkbp:bfsParent gptkb:David_S._Johnson
gptkbp:bfsLayer 4