Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Chen, Hubie; Grohe, Martin License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-8022


Constraint Satisfaction with Succinctly Specified Relations



The general intractability of the constraint satisfaction problem has motivated the study of the complexity of restricted cases of this problem. Thus far, the literature has primarily considered the formulation of the CSP where constraint relations are given explicitly. We initiate the systematic study of CSP complexity with succinctly specified constraint relations. This is joint work with Hubie Chen.

BibTeX - Entry

  author =	{Hubie Chen and Martin Grohe},
  title =	{Constraint Satisfaction with Succinctly Specified Relations},
  booktitle =	{Complexity of Constraints},
  year =	{2006},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  number =	{06401},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Constraint satisfaction, complexity, succinct representations}

Keywords: Constraint satisfaction, complexity, succinct representations
Seminar: 06401 - Complexity of Constraints
Issue date: 2006
Date of publication: 15.11.2006

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