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).
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
|Look up in GoogleScholar|