Tractable tree convex constraint networks

Yuanlin Zhang, Eugene C. Freuder

Research output: Contribution to conferencePaperpeer-review

4 Scopus citations

Abstract

A binary constraint network is tree convex if we can construct a tree for the domain of the variables so that for any constraint, no matter what value one variable takes, all the values allowed for the other variable form a subtree of the constructed tree. It is known that a tree convex network is globally consistent if it is path consistent. However, if a tree convex network is not path consistent, enforcing path consistency on it may not make it globally consistent. In this paper, we identify a subclass of tree convex networks which are locally chain convex and union closed. This class of problems can be made globally consistent by path consistency and thus is tractable. More interestingly, we also find that some scene labeling problems can be modeled by tree convex constraints in a natural and meaningful way.

Original languageEnglish
Pages197-202
Number of pages6
StatePublished - 2004
EventProceedings - Nineteenth National Conference on Artificial Intelligence (AAAI-2004): Sixteenth Innovative Applications of Artificial Intelligence Conference (IAAI-2004) - San Jose, CA, United States
Duration: Jul 25 2004Jul 29 2004

Conference

ConferenceProceedings - Nineteenth National Conference on Artificial Intelligence (AAAI-2004): Sixteenth Innovative Applications of Artificial Intelligence Conference (IAAI-2004)
CountryUnited States
CitySan Jose, CA
Period07/25/0407/29/04

Fingerprint Dive into the research topics of 'Tractable tree convex constraint networks'. Together they form a unique fingerprint.

Cite this