Bulatov, A. and Krokhin, A. and Larose, B. (2008) 'Dualities for constraint satisfaction problems.', in Complexity of constraints : an overview of current research themes. Berlin: Springer, pp. 93-124. Lecture notes in computer science. (5250).
Abstract
In a nutshell, a duality for a constraint satisfaction problem equates the existence of one homomorphism to the non-existence of other homomorphisms. In this survey paper, we give an overview of logical, combinatorial, and algebraic aspects of the following forms of duality for constraint satisfaction problems: finite duality, bounded pathwidth duality, and bounded treewidth duality.
Item Type: | Book chapter |
---|---|
Full text: | Full text not available from this repository. |
Publisher Web site: | http://dx.doi.org/10.1007/978-3-540-92800-3_5 |
Date accepted: | No date available |
Date deposited: | No date available |
Date of first online publication: | 2008 |
Date first made open access: | No date available |
Save or Share this output
Export: | |
Look up in GoogleScholar |