In this paper, we study constraint satisfaction over connected row convex (CRC) constraints, a large class of constraints subsuming, in particular, monotone constriants. We first show that CRC constraints are closed under composition, intersection, and transposition, the basic operations of path-consistency algorithms. This establishes that path consistency over CRC constraints produces a minimal and decomposable network, strenghtening the results of van Beek and Dechter (1995). We then present a path-consistency algorithm for CRC constraints running in time O(n~3d~2) and space O(n~2d), where n is the number of variables and d is the size of the largest domain. This improves the traditional time complexity O(n~3d~3) and space complexity O(n~3d~2). Finally, we show that a solution can be found in time O(n~2), once the graph is path-consistent.
展开▼
