Journal article icon

Journal article

Generalizing constraint satisfaction on trees: Hybrid tractability and variable elimination

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 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
Publication status:
Published

Actions


Access Document


Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Journal:
ARTIFICIAL INTELLIGENCE
Volume:
174
Issue:
9-10
Pages:
570-584
Publication date:
2010-06-01
DOI:
ISSN:
0004-3702
Source identifiers:
298782
Language:
English
Keywords:
Pubs id:
pubs:298782
UUID:
uuid:0c27a2d9-81c3-4116-9615-51886f496bc6
Local pid:
pubs:298782
Deposit date:
2012-12-19

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP