Journal of the ACM Bibliography
Peter Jeavons, David Cohen, and Marc Gyssens. Closure properties
of constraints. Journal of the ACM, 44(4):527-548, July
1997.
[BibTeX entry]
Categories and Subject Descriptors:
F.1.3 [Computation by Abstract Devices]: Complexity
Classes -- reducibility and completeness; F.2.2
[Analysis of Algorithms and Problem Complexity]:
Nonnumerical Algorithms and Problems -- complexity of proof
procedures; F.4.1 [Mathematical Logic and Formal
Languages]: Mathematical Logic; G.2.1 [Discrete
Mathematics]: Combinatorics
General Terms:
Algorithms, Languages, Theory, Verification
Additional Key Words and Phrases:
Complexity, constraint satisfaction problem, indicator problem,
NP-completeness
Selected references
- E. F. Codd. A relational model of data for large shared data banks.
Communications of the ACM, 13(6):377-387, June 1970. Also
published in/as: `Readings in Database Systems', M. Stonebraker,
Morgan-Kaufmann, 1988, pp. 5-15.
- Tomás Feder and Moshe Y. Vardi. Monotone monadic SNP and
constraint satisfaction. In Proceedings of the Twenty-Fifth
Annual ACM Symposium on the Theory of Computing, pages 612-622,
San Diego, California, 16-18 May 1993.
- Eugene C. Freuder. A
sufficient condition for backtrack-bounded search. Journal of
the ACM, 32(4):755-761, October 1985.
- Peter B. Ladkin and Roger D. Maddux. On binary constraint problems.
Journal of the ACM, 41(3):435-469, May 1994.
- Thomas J. Schaefer. The complexity of
satisfiability problems. In Conference Record of the Tenth
Annual ACM Symposium on Theory of Computing, pages 216-226, San
Diego, California, 1-3 May 1978.
Shortcuts: