Perfect Constraints Are Tractable

Journal article

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. © 2008 Springer-Verlag Berlin Heidelberg.

Authors: Salamon, A; Jeavons, P

• Publication status: Published
• Journal: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING
• Volume: 5202
• Pages: 524-528
• Publication date: 2008-01-01
• DOI: 10.1007/978-3-540-85958-1_35
• EISSN: 1611-3349
• ISSN: 0302-9743
• Language: English