---
title: "Constraint Satisfaction over Connected Row Convex Constraints"
authors:
  - "Yves Deville"
  - "Olivier Barette"
  - "Pascal Van Hentenryck"
doi: ""
url: "https://ijcai.org/proceedings/1997/60"
pdf: "https://ijcai.org/proceedings/1997/0060.pdf"
venue: "Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence"
year: 1997
pages: "405-410"
track: "Constraint Satisfaction"
keywords:
---

# Constraint Satisfaction over Connected Row Convex Constraints

Yves Deville, Olivier Barette, Pascal Van Hentenryck

*Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence*, pages 405-410.

## 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 0( n 3 d2 ) and space O(n 2 d), where n is th e number of variables and d is the size of the largest domain. This improves the traditional time complexity O(n3 d3 ) and space complexity O(n3 d2 ) . Finally, we show that a solution can be found in time O(n 2 ), once the graph is path-consistent.