Perfect Constraints Are Tractable
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 stru...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Springer
2008
|
| _version_ | 1826342832419373056 |
|---|---|
| author | Salamon, A Jeavons, P |
| author_facet | Salamon, A Jeavons, P |
| author_sort | Salamon, A |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T02:57:57Z |
| format | Conference item |
| id | oxford-uuid:aff77442-37e6-458b-b8fe-37999d4d6b6c |
| institution | University of Oxford |
| last_indexed | 2024-03-07T02:57:57Z |
| publishDate | 2008 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:aff77442-37e6-458b-b8fe-37999d4d6b6c2022-03-27T03:53:02ZPerfect Constraints Are TractableConference itemhttp://purl.org/coar/resource_type/c_5794uuid:aff77442-37e6-458b-b8fe-37999d4d6b6cDepartment of Computer ScienceSpringer2008Salamon, AJeavons, PBy 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. |
| spellingShingle | Salamon, A Jeavons, P Perfect Constraints Are Tractable |
| title | Perfect Constraints Are Tractable |
| title_full | Perfect Constraints Are Tractable |
| title_fullStr | Perfect Constraints Are Tractable |
| title_full_unstemmed | Perfect Constraints Are Tractable |
| title_short | Perfect Constraints Are Tractable |
| title_sort | perfect constraints are tractable |
| work_keys_str_mv | AT salamona perfectconstraintsaretractable AT jeavonsp perfectconstraintsaretractable |