Generalizing constraint satisfaction on trees: Hybrid tractability and variable elimination

Journal article

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 novel tractable class for this problem which significantly generalizes the class of problems with tree structure. We show that the broken-triangle property is c...

Expand abstract

Authors: Cooper, M; Jeavons, P; Salamon, A

• Publication status: Published
• Journal: ARTIFICIAL INTELLIGENCE
• Volume: 174
• Issue: 9-10
• Pages: 570-584
• Publication date: 2010-06-01
• DOI: 10.1016/j.artint.2010.03.002
• ISSN: 0004-3702
• Language: English
• Keywords: Variable elimination; Arc consistency; Constraint satisfaction; Tractability; Computational complexity; Variable ordering