Constraint Satisfaction Problems
Computational problems from many different application areas can be seen as constraint satisfaction problems. For example, the problems of scheduling a collection of tasks, or laying out a silicon chip, or interpreting a visual image, can all be seen in this way. In any constraint satisfaction problem there is a collection of variables which all have to be assigned values, subject to specified constraints. An equivalent way of definining constraint satisfaction problems is via homomorphisms between relational structures. Our goal is to understand the computational complexity of constraint satisfaction problems.
Head of Activity
Minimal Weighted Clones with Boolean Support
Tractable Classes of Binary CSPs Defined by Excluded Topological Minors
David A. Cohen‚ Martin C. Cooper‚ Peter Jeavons and Stanislav Živný
In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI'15). Pages 1945–1951. AAAI Press. 2015.
The complexity of valued constraint satisfaction
Peter Jeavons‚ Andrei Krokhin and Stanislav Živný
In Bulletin of the European Association for Theoretical Computer Science (EATCS). Vol. 113. Pages 21−55. 2014.
Errata can be found here.