Hybrid tractable CSPs which generalize tree structure
Martin C. Cooper‚ Peter G. Jeavons and András Z. Salamon
Abstract
The constraint satisfaction problem (CSP) is a central generic problem in artificial intelligence. Considerable progress has been made in identifying properties which ensure tractability in such problems, such as the property of being tree-structured. In this paper we introduce the broken-triangle property, which allows us to define a hybrid tractable class for this problem which significantly generalizes the class of problems with tree structure. We show that the broken-triangle property is conservative (i.e., it is preserved under domain reduction and hence under arc consistency operations) and that there is a polynomial-time algorithm to determine an ordering of the variables for which the broken-triangle property holds (or to determine that no such ordering exists). We also present a non-conservative extension of the broken-triangle property which is also sufficient to ensure tractability and can be detected in polynomial time.
Details
| Book Title |
ECAI 2008‚ Proceedings of the 18th European Conference on Artificial Intelligence‚ July 21–25‚ Patras‚ Greece |
| Editor |
Malik Ghallab‚ Constantine D. Spyropoulos‚ Nikos Fakotakis‚ Nikos Avouris |
| ISBN |
978−1−58603−891−5 |
| ISSN |
0922−6389 |
| Note |
Best paper award. |
| Pages |
530–534 |
| Publisher |
IOS Press |
| Series |
Frontiers in Artificial Intelligence and Applications |
| Volume |
178 |
| Year |
2008 |
Links
Related pages
|
People |
|
|
Activities |