Building tractable disjunctive constraints
Many combinatorial search problems can be expressed as 'constraint satisfaction problems'. This class of problems is known to be NP-hard in general, but a number of restricted constraint classes have been identified which ensure tractability. This paper presents the first general results o...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2000
|
| _version_ | 1826259067206631424 |
|---|---|
| author | Cohen, D Jeavons, P Jonsson, P Koubarakis, M |
| author_facet | Cohen, D Jeavons, P Jonsson, P Koubarakis, M |
| author_sort | Cohen, D |
| collection | OXFORD |
| description | Many combinatorial search problems can be expressed as 'constraint satisfaction problems'. This class of problems is known to be NP-hard in general, but a number of restricted constraint classes have been identified which ensure tractability. This paper presents the first general results on combining tractable constraint classes to obtain larger, more general, tractable classes. We give examples to show that many known examples of tractable constraint classes, from a wide variety of different contexts, can be constructed from simpler tractable classes using a general method. We also construct several new tractable classes that have not previously been identified. © 2000 ACM. |
| first_indexed | 2024-03-06T18:44:00Z |
| format | Journal article |
| id | oxford-uuid:0de17b9f-8994-42c8-90d4-9d677cf4df44 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T18:44:00Z |
| publishDate | 2000 |
| record_format | dspace |
| spelling | oxford-uuid:0de17b9f-8994-42c8-90d4-9d677cf4df442022-03-26T09:42:46ZBuilding tractable disjunctive constraintsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:0de17b9f-8994-42c8-90d4-9d677cf4df44EnglishSymplectic Elements at Oxford2000Cohen, DJeavons, PJonsson, PKoubarakis, MMany combinatorial search problems can be expressed as 'constraint satisfaction problems'. This class of problems is known to be NP-hard in general, but a number of restricted constraint classes have been identified which ensure tractability. This paper presents the first general results on combining tractable constraint classes to obtain larger, more general, tractable classes. We give examples to show that many known examples of tractable constraint classes, from a wide variety of different contexts, can be constructed from simpler tractable classes using a general method. We also construct several new tractable classes that have not previously been identified. © 2000 ACM. |
| spellingShingle | Cohen, D Jeavons, P Jonsson, P Koubarakis, M Building tractable disjunctive constraints |
| title | Building tractable disjunctive constraints |
| title_full | Building tractable disjunctive constraints |
| title_fullStr | Building tractable disjunctive constraints |
| title_full_unstemmed | Building tractable disjunctive constraints |
| title_short | Building tractable disjunctive constraints |
| title_sort | building tractable disjunctive constraints |
| work_keys_str_mv | AT cohend buildingtractabledisjunctiveconstraints AT jeavonsp buildingtractabledisjunctiveconstraints AT jonssonp buildingtractabledisjunctiveconstraints AT koubarakism buildingtractabledisjunctiveconstraints |