On tree-preserving constraints

Publisher:
Springer International Publishing
Publication Type:
Conference Proceeding
Citation:
21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings, 2015, 9255
Issue Date:
2015-08-31
Full metadata record
Files in This Item:
Filename Description Size
On_Tree-Preserving_Constraints.pdfAccepted Manuscript Version462.26 kB
Adobe PDF
Tree convex constraints are extensions of the well-known row convex constraints. Just like the latter, every path-consistent tree convex constraint network is globally consistent. This paper studies and compares three subclasses of tree convex constraints which are called chain-, path- and tree-preserving constraints respectively. While the tractability of the subclass of chain-preserving constraints has been established before, this paper shows that every chain- or path-preserving constraint network is in essence the disjoint union of several independent connected row convex constraint networks, and hence (re-)establish the tractability of these two subclasses of tree convex constraints. We further prove that, when enforcing arc- and path-consistency on a tree-preserving constraint network, in each step, the network remains tree-preserving. This ensures the global consistency of the tree-preserving network if no inconsistency is detected. Moreover, it also guarantees the applicability of the partial path-consistency algorithm to tree-preserving constraint networks, which is usually more efficient than the path-consistency algorithm for large sparse networks. As an application, we show that the class of tree-preserving constraints is useful in solving the scene labelling problem.
Please use this identifier to cite or link to this item: