Cookies

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).

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
Record Created:15 Dec 2009 14:35
Last Modified:05 Jan 2010 10:44

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library