TY - JOUR
T1 - Properties of tree convex constraints
AU - Zhang, Yuanlin
AU - Freuder, Eugene C.
N1 - Funding Information:
✩ A preliminary version of this paper appeared in [Y. Zhang, E.C. Freuder, Tractable tree convex constraints, in: Proceedings of National Conference on Artificial Intelligence 2004, San Jose, CA, USA, AAAI Press, 2004, pp. 197–202]. ✩✩ This material is based in part upon works supported by the Science Foundation Ireland under Grants No. 00/PI.1/C075 and No. 05/IN/1886. * Corresponding author. E-mail addresses: yzhang@cs.ttu.edu (Y. Zhang), e.freuder@4c.ucc.ie (E.C. Freuder).
PY - 2008/8
Y1 - 2008/8
N2 - 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.
AB - 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.
KW - (Connected) row convex constraints
KW - Constraint networks
KW - Global consistency
KW - Local consistency
KW - Locally chain convex and strictly union closed constraints
KW - Scene labeling problem
KW - Tree convex constraints
UR - http://www.scopus.com/inward/record.url?scp=46549089986&partnerID=8YFLogxK
U2 - 10.1016/j.artint.2008.05.001
DO - 10.1016/j.artint.2008.05.001
M3 - Article
AN - SCOPUS:46549089986
VL - 172
SP - 1605
EP - 1612
JO - Artificial Intelligence
JF - Artificial Intelligence
SN - 0004-3702
IS - 12-13
ER -