Constraint Satisfaction over Connected Row Convex Constraints

Deville, Yves; Barette, Olivier; Van Hentenryck, Pascal

Constraint Satisfaction over Connected Row Convex Constraints

Yves Deville, Olivier Barette, Pascal Van Hentenryck

Download BibTeX Cite

Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. 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.

Yves Deville, Olivier Barette, and Pascal Van Hentenryck. 1997. Constraint Satisfaction over Connected Row Convex Constraints. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97. IJCAI, 405–410. https://ijcai.org/proceedings/1997/60

@inproceedings{ijcai1997p60,
  title     = {Constraint Satisfaction over Connected Row Convex Constraints},
  author    = {Deville, Yves and Barette, Olivier and Van Hentenryck, Pascal},
  booktitle = {Proceedings of the Fifteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-97}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Martha E. Pollack},
  pages     = {405--410},
  year      = {1997},
  note      = {Constraint Satisfaction},
  url       = {https://ijcai.org/proceedings/1997/60},
}

TY  - CPAPER
TI  - Constraint Satisfaction over Connected Row Convex Constraints
AU  - Deville, Yves
AU  - Barette, Olivier
AU  - Van Hentenryck, Pascal
T2  - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1997
SP  - 405
EP  - 410
UR  - https://ijcai.org/proceedings/1997/60
ER  -