We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Dualities for constraint satisfaction problems.

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:
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