In this paper, we study constraint satisfaction over connected row convex (CRC) constraints, a large class of constraints subsuming, in particular, monotone constraints. We rst 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 3 d 2 ) and space O(n 2 d), where n is the number of variables and d is the size of the largest domain. This improves the traditional time complexity O(n 3 d 3 ) and space complexity O(n 3 d 2 ). Finally, we show that a solution can be found in time O(n 2 ), once the graph is path-consistent.
For the class of CRC constraints, a path consistency based algorithm was proposed in REF that runs in
Constraint Satisfaction over Connected Row Convex Constraints
Artificial Intelligence
Computer Science