Fast Algorithm for Connected Row Convex Constraints

Yuanlin Zhang

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.

Subjects: 15.2 Constraint Satisfaction; 9.2 Computational Complexity

Submitted: Oct 10, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.