Proceedings

Fast Algorithm for Connected Row Convex Constraints

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 192-196.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

Many interesting tractable problems are identified under the model of Constraint Satisfaction Problems. These problems are usually solved by forcing a certain level of local consistency. In this paper, for the class of connected row convex constraints, we propose a novel algorithm which is based on the ideas of variable elimination and efficient composition of row convex and connected constraints. Compared with the existing work including randomized algorithms, the new algorithm has better worst case time and space complexity.

  1. [Bliek and Sam-Haroud, 1999] Christian Bliek and Djamila Sam-Haroud. Path consistency on triangulated constraint graphs. In IJCAI-99, pages 456-461, Stockholm, Sweden, 1999. IJCAI Inc.
  2. [Deville et al., 1997] Y. Deville, O. Barette, and P. Van Hen- tenryck. Constraint satisfaction over connected row con- vex constraints. In IJCAI-97, volume 1, pages 405-411, Nagoya, Japan, 1997. IJCAI Inc. IJCAI
  3. [Kumar, 2006] T. K. Satish Kumar. Simple randomized al- gorithms for tractable row and tree convex constraints. In Proceedings of National Conference on Artificial Intelli- gence 2006, page to appear, 2006.
  4. [van Beek and Dechter, 1995] P. van Beek and R. Dechter. On the minimality and global consistency of row-convex constraint networks. Journal of The ACM, 42(3):543-561, 1995.
  5. [Zhang and Yap, 2003] Yuanlin Zhang and Roland H. C. Yap. Consistency and set intersection. In Proceedings of International Joint Conference on Artificial Intelligence 2003, pages 263-268, Acapulco, Mexico, 2003. IJCAI Inc. IJCAI

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards