Conference item icon

Conference item

Classes of submodular constraints expressible by graph cuts

Abstract:

Submodular constraints play an important role both in theory and practice of valued constraint satisfaction problems (VCSPs). It has previously been shown, using results from the theory of combinatorial optimisation, that instances of VCSPs with submodular constraints can be minimised in polynomial time. However, the general algorithm is of order O(n^6) and hence rather impractical. In this paper, by using results from the theory of pseudo-Boolean optimisation, we identify several broad class...

Expand abstract

Actions


Access Document


Publisher copy:
10.1007/978-3-540-85958-1_8

Authors


Stanislav Živný More by this author
Peter G. Jeavons More by this author
Volume:
5202
Publication date:
2008
DOI:
URN:
uuid:7fa94a8c-7819-4a3e-aa39-ca4731df153f
Local pid:
cs:2331

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