Supermodular functions and the complexity of MAX CSP

David Cohen; Martin Cooper; Peter Jeavons; Andrei Krokhin

doi:10.1016/j.dam.2005.03.003

Supermodular functions and the complexity of MAX CSP

David Cohen, Martin Cooper, Peter Jeavons, Andrei Krokhin

Department of Computer Science

Research output: Contribution to journal › Article › peer-review

Original language	English
Pages (from-to)	53-72
Number of pages	20
Journal	Discrete Applied Mathematics
Volume	149
DOIs	https://doi.org/10.1016/j.dam.2005.03.003
Publication status	Published - 2005

Access to Document

10.1016/j.dam.2005.03.003

http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/DAMsupermodular.pdf

Cite this

@article{20202eecf0eb43a7bed9fb2b2a8efc40,

title = "Supermodular functions and the complexity of MAX CSP",

author = "David Cohen and Martin Cooper and Peter Jeavons and Andrei Krokhin",

note = "Earlier version appeared as Identifying efficiently solvable cases of Max CSP \textbackslash{}http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/STACS04maxCSP.ps in: Proceedings of STACS'04, Lecture Notes in Computer Science 2996 (2004)",

year = "2005",

doi = "10.1016/j.dam.2005.03.003",

language = "English",

volume = "149",

pages = "53--72",

journal = "Discrete Applied Mathematics",

issn = "1872-6771",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Supermodular functions and the complexity of MAX CSP

AU - Cohen, David

AU - Cooper, Martin

AU - Jeavons, Peter

AU - Krokhin, Andrei

N1 - Earlier version appeared as Identifying efficiently solvable cases of Max CSP \http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/publications/STACS04maxCSP.ps in: Proceedings of STACS'04, Lecture Notes in Computer Science 2996 (2004)

PY - 2005

Y1 - 2005

U2 - 10.1016/j.dam.2005.03.003

DO - 10.1016/j.dam.2005.03.003

M3 - Article

SN - 1872-6771

VL - 149

SP - 53

EP - 72

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -