2 Search Results for "Schnoor, Ilka"

Document

Enumerating all Solutions for Constraint Satisfaction Problems

Authors: Henning Schnoor and Ilka Schnoor

Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{schnoor_et_al:DagSemProc.06401.6,
  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 =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.6},
  URN =		{urn:nbn:de:0030-drops-8040},
  doi =		{10.4230/DagSemProc.06401.6},
  annote =	{Keywords: Complexity, constraint satisfaction, enumeration}
}

Document

DOI: 10.4230/DagSemProc.06401.7

New Algebraic Tools for Constraint Satisfaction

Authors: Henning Schnoor and Ilka Schnoor

Published in: Dagstuhl Seminar Proceedings, Volume 6401, Complexity of Constraints (2006)

Abstract

The Galois correspondence involving polymorphisms and co-clones has received a lot of attention in regard to constraint satisfaction problems. However, it fails if we are interested in a reduction giving equivalence instead of only satisfiability-equivalence. We show how a similar Galois connection involving weaker closure operators can be applied for these problems. As an example of the usefulness of our construction, we show how to obtain very short proofs of complexity classifications in this context.

Cite as

Henning Schnoor and Ilka Schnoor. New Algebraic Tools for Constraint Satisfaction. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{schnoor_et_al:DagSemProc.06401.7,
  author =	{Schnoor, Henning and Schnoor, Ilka},
  title =	{{New Algebraic Tools for Constraint Satisfaction}},
  booktitle =	{Complexity of Constraints},
  pages =	{1--18},
  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 =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06401.7},
  URN =		{urn:nbn:de:0030-drops-8057},
  doi =		{10.4230/DagSemProc.06401.7},
  annote =	{Keywords: Constraints, Partial Clones, Galois Correspondence}
}

Refine by Author
2 Schnoor, Henning
2 Schnoor, Ilka

Refine by Classification

Refine by Keyword
1 Complexity
1 Constraints
1 Galois Correspondence
1 Partial Clones
1 constraint satisfaction
Show More...

Refine by Type
2 document

Refine by Publication Year
2 2006

2 Search Results for "Schnoor, Ilka"

Enumerating all Solutions for Constraint Satisfaction Problems

Abstract

Cite as

New Algebraic Tools for Constraint Satisfaction

Abstract

Cite as

Thanks for your feedback!

Could not send message