Constraint satisfaction over connected row-convex constraints

This paper studies constraint satisfaction over connected row-convex (CRC) constraints. It shows that CRC constraints are closed under composition, in tersection, and transposition, the basic operations of path-consistency alg orithms. This establishes that path consistency over CRC constraints produc es a minimal and decomposable network and is thus a polynomial-time decisio n procedure for CRC networks. This paper also presents a new path-consisten cy 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 d omain, improving the traditional time and space complexity by orders of mag nitude. The paper also shows how to construct CRC constraints by conjunctio n and disjunction of a set of basic CRC constraints, highlighting how CRC c onstraints generalize monotone constraints and presenting interesting subcl asses of CRC constraints. Experimental results show that the algorithm beha ves well in practice. (C) 1999 Elsevier Science B.V. All rights reserved.