Perfect Constraints Are Tractable
András Z. Salamon and Peter G. Jeavons
Abstract
By using recent results from graph theory, including the Strong Perfect Graph Theorem, we obtain a unifying framework for a number of tractable classes of constraint problems. These include problems with chordal microstructure; problems with chordal microstructure complement; problems with tree structure; and the ``all-different'' constraint. In each of these cases we show that the associated microstructure of the problem is a perfect graph, and hence they are all part of the same larger family of tractable problems.
Details
| Book Title |
Proceedings of the 14th International Conference on Principles and Practice of Constraint Programming‚ CP 2008‚ Sydney‚ Australia‚ 14–18 September |
| ISBN |
978−3−540−85957−4 |
| Pages |
524−528 |
| Publisher |
Springer |
| Series |
Lecture Notes in Computer Science |
| Volume |
5202 |
| Year |
2008 |
Links
DOI (10.1007/978-3-540-85958-1_35)
Related pages
|
People |
|
|
Activities |