License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-8017
URL: http://drops.dagstuhl.de/opus/volltexte/2006/801/
Go to the corresponding Portal


Cohen, David ; Gyssens, Marc ; Jeavons, Peter

A Unifying Theory of Structural Decompostions for the Constraint Satisfaction Problems

pdf-format:
Document 1.pdf (335 KB)


Abstract

In this talk (draft paper) we develop the theory of structural decompositions for the CSP. We begin with the very general notion of a guarded decomposition and make several simplifying assumptions to arrive a the definition of an acyclic guarded cover. We show how many existing decompositions can seen as acyclic guarded covers. We develop a generic algorithm for discovering acyclic guarded covers under the further assumption that they have a join tree satisfying a simple extra condition. We show that many existing decompositions do in fact satisfy this extra condition. Using this theory we are able to describe a new class of structural decompostion which we call spread cuts. These generalise many existing decomposition methods. We present a class of hypergraphs whose spread cut width is significantly smaller than their hypertree width. The definition of a guarded decomposition and the algorithm for discovering them were motvated by the similar algorithms developed by Gottlob, Scarcello and Leone in their work on hypertrees. The authors also wish to acknowledge that an acyclic guarded decomposition is very similar to a generalised hypertree decomposition as described in the hypertree literature.

BibTeX - Entry

@InProceedings{cohen_et_al:DSP:2006:801,
  author =	{David Cohen and Marc Gyssens and Peter Jeavons},
  title =	{A Unifying Theory of Structural Decompostions for the Constraint Satisfaction Problems},
  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 =		{http://drops.dagstuhl.de/opus/volltexte/2006/801},
  annote =	{Keywords: Structural decomposition, spread cut}
}

Keywords: Structural decomposition, spread cut
Seminar: 06401 - Complexity of Constraints
Issue Date: 2006
Date of publication: 15.11.2006


DROPS-Home | Fulltext Search | Imprint Published by LZI