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:

Majority constraints have bounded pathwidth duality.

Dalmau, V. and Krokhin, A. (2008) 'Majority constraints have bounded pathwidth duality.', European journal of combinatorics., 29 (4). pp. 821-837.

Abstract

We study certain constraint satisfaction problems which are the problems of deciding whether there exists a homomorphism from a given relational structure to a fixed structure with a majority polymorphism. We show that such a problem is equivalent to deciding whether the given structure admits a homomorphism from an obstruction belonging to a certain class of structures of bounded pathwidth. This implies that the constraint satisfaction problem for any fixed structure with a majority polymorphism is in NL.

Item Type:Article
Full text:Full text not available from this repository.
Publisher Web site:http://dx.doi.org/10.1016/j.ejc.2007.11.020
Record Created:18 Dec 2009 11:05
Last Modified:05 Jan 2010 11:01

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