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|
|Record Created:||15 Dec 2009 14:35|
|Last Modified:||05 Jan 2010 10:44|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|