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

@inproceedings{Garey1978ComputersAI, title={Computers and Intractability: A Guide to the Theory of NP-Completeness}, author={M. R. Garey and David S. Johnson}, year={1978} }

#### Topics from this paper

#### 48,686 Citations

Quasi-Acyclic Propositional Horn Knowledge Bases: Optimal Compression

- Mathematics, Computer Science
- IEEE Trans. Knowl. Data Eng.
- 1995

The paper is concerned with the optimal compression of propositional Horn production rule bases-one of the most important knowledge bases used in practice and develops a procedure and algorithm for recognizing in quadratic time the quasi acyclicity of a function given by a Horn CNF. Expand

Graph-based methods for Horn knowledge compression

- Computer Science
- 1994 Proceedings of the Twenty-Seventh Hawaii International Conference on System Sciences
- 1994

The paper is concerned with the optimal compression of propositional Horn production rule bases/spl minus/one of the most important knowledge bases used in practice and develops a procedure and algorithm for recognizing in quadratic time the quasi-acyclicity of a function given by a Horn CNF. Expand

On the Hardness of Approximate Reasoning

- Mathematics, Computer Science
- IJCAI
- 1993

It is proved that counting satisfying assignments of propositional languages is intractable even for Horn and monotone formulae, and even when the size of clauses and number of occurrences of the variables are extremely limited. Expand

Reasoning with Propositional Logic: From SAT Solvers to Knowledge Compilation

- Computer Science
- 2020

This chapter presents the kind of A.I. problems that can typically be addressed by the Propositional Logic, and presents an historical view of the impressive progresses observed in the practical solving of the Satisfiability (SAT) problem. Expand

The complexity of minimum partial truth assignments and implication in negation-free formulae

- Mathematics, Computer Science
- Annals of Mathematics and Artificial Intelligence
- 2005

It is argued that these results are relevant, first to areas where a least solution (in some fashion) is desired, and second, to limited deductive systems. Expand

Horn minimization by iterative decomposition

- Mathematics, Computer Science
- Annals of Mathematics and Artificial Intelligence
- 2004

A linear time algorithm is presented which takes a Horn CNF as an input, and through a series of decompositions reduces the minimization of the input CNF to the minimized problem on a“shorter” CNF. Expand

Applications of General Exact Satisfiability in Propositional Logic Modelling

- Mathematics, Computer Science
- LPAR
- 2004

It is shown that c-atoms can be efficiently reduced to a general form of Exact Satisfiability and the general x i sat problem, to find an assignment for a CNF such that exactly i literals are true in each clause for any i ≥ 1, is solvable in time O(1.4143 n). Expand

Propositional satisfiability in declarative programming

- Computer Science, Mathematics
- ArXiv
- 2002

This paper proposes two logics based on predicate calculus as formalisms for encoding search problems and shows that the expressive power of these logics is given by the class NP-search. Expand

Formula dissection: A parallel algorithm for constraint satisfaction

- Computer Science
- Comput. Math. Appl.
- 2008

This paper presents a simple and relatively efficient parallel divide-and-conquer method to solve various subclasses of SAT and derives a parallel algorithm for the class of formulae whose corresponding graph representation is planar. Expand

TR-2007008: The Satisfiability Problem—From the Theory of NP-Completeness to State-of-the-Art SAT Solvers

- Computer Science
- 2003

SAT is introduced through the theory of NP-completeness, and a broad overview of the different techniques and algorithms used to solve the SAT problem is followed, noting that given vast amount of algorithms that have been proposed only the classical and most prominent are discussed. Expand

#### References

SHOWING 1-10 OF 25 REFERENCES

Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time

- Computer Science, Mathematics
- SIAM J. Algebraic Discret. Methods
- 1980

An algorithm to solve the problem of testing the bandwidth of a graph in time, which implies that the “Bandwidth $\overset{?}{\leqq} k$” problem is not NP-complete (unless P = NP) for any fixed k. Expand

Two papers on graph embedding problems

- Mathematics
- 1980

Abstract : This report contains two independent papers on problems concerned with graph embedding-i.e., assignment of the vertices of a graph to points in a metric space subject to specified… Expand

Some theoretical aspects of position-location problems

- Computer Science
- 20th Annual Symposium on Foundations of Computer Science (sfcs 1979)
- 1979

Among the major results presented is the discovery of a large class of geometrical decision problems, all of which are randomly decidable (i.e., decidable by a probabilistic polynomial-time algorithm), but many of which seem to be Intractable. Expand

Area-Efficient Graph Layouts (for VLSI).

- Computer Science
- FOCS 1980
- 1980

An algorithm is given that produces VLSI layouts for classes of graphs that have good separator theorems and shows in particular that any planar graph of n vertices has an O(n lg-square(n) area layout and that any tree of n Vertices can be laid out in linear area. Expand

An application of graph coloring to printed circuit testing

- Computer Science
- 16th Annual Symposium on Foundations of Computer Science (sfcs 1975)
- 1975

Under certain assumptions on the possible types of short circuits, the structure of line-of-sight graphs is analyzed and it is shown that a well-known and efficient algorithm can be used to color them with a small number of colors. Expand

Uniform Data Encodings

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1980

This work has shown that finding uniform encodings, even when the guest is a line, is PSPACE-complete, and there is a linear time algorithm for nonuniform encoding of lines in graphs. Expand

On the Area of Binary Tree Layouts

- Mathematics, Computer Science
- Inf. Process. Lett.
- 1980

This note shows that it is not possible to design a complete binary tree layout with area O(n) and all leaves on the boundary, if the boundary of the chip is a convex plane curve and the leaves onThe boundary are separated by at least unit distance, then area of order nlogn is necessary just to accomodate all the wires. Expand

Tidy Drawings of Trees

- Computer Science
- IEEE Transactions on Software Engineering
- 1979

Two naive tree drawers are surveyed, formalize aesthetics for tidy trees, and two algorithms which draw tidy trees are discussed, one of which may be shown to require the minimum possible paper width. Expand

The node cost measure for embedding graphs on the planar grid (Extended Abstract)

- Computer Science
- STOC '80
- 1980

This paper is primarily concerned with a third measure, total number of nodes, which can be modeled by allowing the insertion of nodes along edges of the graph and then insisting that the embedding may not bend edges. Expand

Grammar and L forms: An introduction

- Art, Mathematics
- Lecture Notes in Computer Science
- 1980

A comparison study of context-free grammar forms for EOL and ETOL forms and their applications in education, research and teaching. Expand