Computers and intractability. A guide to the theory of NP-completeness. (English) Zbl 0411.68039

Garey, Michael R.; Johnson, David S.

A Series of Books in the mathematical Sciences. San Francisco: W. H. Freeman and Company. X, 338 p. (1979).

MSC:

68Q25	Analysis of algorithms and problem complexity
68-02	Research exposition (monographs, survey articles) pertaining to computer science
03D15	Complexity of computation (including implicit computational complexity)
68R10	Graph theory (including graph drawing) in computer science
94C15	Applications of graph theory to circuits and networks
94C30	Applications of design theory to circuits and networks
05A17	Combinatorial aspects of partitions of integers
68P20	Information storage and retrieval of data
68M20	Performance evaluation, queueing, and scheduling in the context of computer systems
90C99	Mathematical programming
90B35	Deterministic scheduling theory in operations research
91A99	Game theory
68Q45	Formal languages and automata
68T99	Artificial intelligence
68N99	Theory of software

Keywords:

NP-completeness; approximation algorithms; computational complexity; graph theory; network design; partitions; storage; retrieval; sequencing; scheduling; mathematical programming; algebra; number theory; games; puzzles; logic; automata; languages; program optimization; polynomial solvable problems