Properties of tree convex constraints

Yuanlin Zhang, Eugene C. Freuder

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

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 investigate the properties of some tree convex constraints under intersection and composition. As a result, we identify a sub-class of tree convex networks that are locally chain convex and strictly union closed. This class of problems can be made globally consistent by arc and path consistency and thus is tractable. Interestingly, we also find that some scene labeling problems can be modeled by tree convex constraints in a natural and meaningful way.

Original languageEnglish
Pages (from-to)1605-1612
Number of pages8
JournalArtificial Intelligence
Volume172
Issue number12-13
DOIs
StatePublished - Aug 2008

Keywords

  • (Connected) row convex constraints
  • Constraint networks
  • Global consistency
  • Local consistency
  • Locally chain convex and strictly union closed constraints
  • Scene labeling problem
  • Tree convex constraints

Fingerprint

Dive into the research topics of 'Properties of tree convex constraints'. Together they form a unique fingerprint.

Cite this