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.
infobook 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
BibTeX
Link (pdf)
related pages
|
