License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06401.5
URN: urn:nbn:de:0030-drops-8022
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/802/
Go to the corresponding Portal |
Chen, Hubie ;
Grohe, Martin
Constraint Satisfaction with Succinctly Specified Relations
Abstract
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
@InProceedings{chen_et_al:DagSemProc.06401.5,
author = {Chen, Hubie and Grohe, Martin},
title = {{Constraint Satisfaction with Succinctly Specified Relations}},
booktitle = {Complexity of Constraints},
pages = {1--15},
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.dagstuhl.de/opus/volltexte/2006/802},
URN = {urn:nbn:de:0030-drops-8022},
doi = {10.4230/DagSemProc.06401.5},
annote = {Keywords: Constraint satisfaction, complexity, succinct representations}
}
Keywords: |
|
Constraint satisfaction, complexity, succinct representations |
Collection: |
|
06401 - Complexity of Constraints |
Issue Date: |
|
2006 |
Date of publication: |
|
15.11.2006 |