Journal article icon

Journal article

Necessary conditions for tractability of valued CSPs

Abstract:

The connection between constraint languages and clone theory has been a fruitful line of research on the complexity of constraint satisfaction problems. In a recent result, Cohen et al. [SICOMP’13] have characterised a Galois connection between valued constraint languages and so-called weighted clones. In this paper, we study the structure of weighted clones. We extend the results of Creed and Zivny from [CP’11/SICOMP’13] on types of weightings necessarily contained in every nontrivial weight...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Files:
Publisher copy:
10.1137/140990346

Authors


Thapper, J More by this author
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Royal Society University Research Fellowship More from this funder
Publisher:
Society for Industrial and Applied Mathematics Publisher's website
Journal:
SIAM Journal on Discrete Mathematics Journal website
DOI:
EISSN:
1095-7146
ISSN:
0895-4801
URN:
uuid:fda16d19-b92a-4b41-af80-e3601bce603d
Source identifiers:
579510
Local pid:
pubs:579510

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP