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.
infobook 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
BibTeX
Link (pdf)
DOI (10.1007/978-3-540-85958-1_35)
related pages
|
