DagSemProc.06401.6.pdf
- Filesize: 404 kB
- 25 pages
Document
Enumerating all Solutions for Constraint Satisfaction Problems
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 6401
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2006-11-15
Cite AsGet BibTex
Henning Schnoor and Ilka Schnoor. Enumerating all Solutions for Constraint Satisfaction Problems. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.06401.6
https://doi.org/10.4230/DagSemProc.06401.6
Abstract
We contribute to the study of efficient enumeration algorithms for all solutions of constraint satisfaction problems. The only algorithm known so far, presented by Creignou and Hébrard and generalized by Cohen, reduces the enumeration problem for a constraint language $Gamma$ to the decision problem for a slightly enlarged constraint language $Gamma^+,$ i.e., it yields an efficient enumeration algorithm for the case where $mathrm{CSP}(Gamma^+)$ is tractable. We develop a new class of algorithms, yielding efficient enumeration algorithms for a broad class of constraint languages. For the three-element domain, we achieve a first step towards a dichotomy theorem for the enumeration problem.
Keywords
- Complexity
- constraint satisfaction
- enumeration
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads