2026-07-20T05:24:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:804 2024-03-06T11:07:06Z ddc:004 open_access

Enumerating all Solutions for Constraint Satisfaction Problems Schnoor, Henning Schnoor, Ilka Complexity constraint satisfaction enumeration 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Henning Schnoor and Ilka Schnoor 2006 Is Part Of Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06401.6 urn:nbn:de:0030-drops-8040 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.6 eng https://creativecommons.org/licenses/by/4.0/legalcode