Document Server@UHasselt >
Research publications >
Please use this identifier to cite or link to this item:
|Title: ||Closure properties of constraints|
|Authors: ||Jeavons, P.|
|Issue Date: ||1997|
|Citation: ||Journal of the ACM, 44(4). p. 527-548|
|Abstract: ||Many combinatorial search problems can be expressed as “constraint satisfaction problems” and this class of problems is known to be NP-complete in general. In this paper, we investigate the subclasses that arise from restricting the possible constraint types. We first show that any set of constraints that does not give rise to an NP-complete class of problems must satisfy a certain type of algebraic closure condition. We then investigate all the different possible forms of this algebraic closure property, and establish which of these are sufficient to ensure tractability. As examples, we show that all known classes of tractable constraints over finite domains can be characterized by such an algebraic closure property. Finally, we describe a simple computational procedure that can be used to determine the closure properties of a given set of constraints. This procedure involves solving a particular constraint satisfaction problem, which we call an “indicator problem.”|
|Link to publication: ||http://doi.acm.org/10.1145/263867.263489|
|Type: ||Journal Contribution|
|Appears in Collections: ||Research publications|
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.