Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Schnoor, Henning; Schnoor, Ilka License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-8040


Enumerating all Solutions for Constraint Satisfaction Problems



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.

BibTeX - Entry

  author =	{Schnoor, Henning and Schnoor, Ilka},
  title =	{{Enumerating all Solutions for Constraint Satisfaction Problems}},
  booktitle =	{Complexity of Constraints},
  pages =	{1--25},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6401},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-8040},
  doi =		{10.4230/DagSemProc.06401.6},
  annote =	{Keywords: Complexity, constraint satisfaction, enumeration}

Keywords: Complexity, constraint satisfaction, enumeration
Seminar: 06401 - Complexity of Constraints
Issue date: 2006
Date of publication: 15.11.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI