Fast Algorithm for Connected Row Convex Constraints

Zhang, Yuanlin

Fast Algorithm for Connected Row Convex Constraints

Download BibTeX Cite

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

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.

Yuanlin Zhang. 2007. Fast Algorithm for Connected Row Convex Constraints. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07. IJCAI, 192–196. https://ijcai.org/proceedings/2007/29

@inproceedings{ijcai2007p29,
  title     = {Fast Algorithm for Connected Row Convex Constraints},
  author    = {Zhang, Yuanlin},
  booktitle = {Proceedings of the Twentieth International Joint Conference on
               Artificial Intelligence, {IJCAI-07}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Ramon López de Mántaras},
  pages     = {192--196},
  year      = {2007},
  url       = {https://ijcai.org/proceedings/2007/29},
}

TY  - CPAPER
TI  - Fast Algorithm for Connected Row Convex Constraints
AU  - Zhang, Yuanlin
T2  - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2007
SP  - 192
EP  - 196
UR  - https://ijcai.org/proceedings/2007/29
ER  -