Yves Deville Olivier Barette 1997

Abstract:  In this paper, we study constraint satisfaction over connected row convex (CRC) constraints, a large class of constraints subsuming, in particular, monotone constraints. 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 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. 1 Introduction Constraint satisfaction techniques have been found useful in many areas such as Ope...