A Generalized Arc-Consistency Algorithm for a Class of Counting Constraints

Petit, Thierry; Beldiceanu, Nicolas; Lorca, Xavier

doi:10.5591/978-1-57735-516-8/IJCAI11-114

A Generalized Arc-Consistency Algorithm for a Class of Counting Constraints

Thierry Petit, Nicolas Beldiceanu, Xavier Lorca

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 643-647.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-114

Abstract

This paper introduces the Seqbin meta-constraint with a polytime algorithm achieving generalized arc-consistency. Seqbin can be used for encoding counting constraints such as Change, Smooth, or InncreasingNValue. For all of them the time and space complexity is linear in the sum of domain sizes, which improves or equals the best known results of the literature.

Thierry Petit, Nicolas Beldiceanu, and Xavier Lorca. 2011. A Generalized Arc-Consistency Algorithm for a Class of Counting Constraints. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 643–647. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-114

@inproceedings{ijcai2011p114,
  title     = {A Generalized Arc-Consistency Algorithm for a Class of Counting Constraints},
  author    = {Petit, Thierry and Beldiceanu, Nicolas and Lorca, Xavier},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {643--647},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-114},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-114},
}

TY  - CPAPER
TI  - A Generalized Arc-Consistency Algorithm for a Class of Counting Constraints
AU  - Petit, Thierry
AU  - Beldiceanu, Nicolas
AU  - Lorca, Xavier
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 643
EP  - 647
DO  - 10.5591/978-1-57735-516-8/IJCAI11-114
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-114
ER  -