ML Anthology

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

Thierry Petit, Nicolas Beldiceanu, Xavier Lorca
IJCAI 2011 pp. 643-648
doi:10.5591/978-1-57735-516-8/IJCAI11-114 /ijcai/2011/petit2011ijcai-generalized/

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.

PDF IJCAI Semantic Scholar

Cite

Text

Petit et al. "A Generalized Arc-Consistency Algorithm for a Class of Counting Constraints." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-114

Markdown

[Petit et al. "A Generalized Arc-Consistency Algorithm for a Class of Counting Constraints." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/petit2011ijcai-generalized/) doi:10.5591/978-1-57735-516-8/IJCAI11-114

BibTeX

@inproceedings{petit2011ijcai-generalized,
  title     = {{A Generalized Arc-Consistency Algorithm for a Class of Counting Constraints}},
  author    = {Petit, Thierry and Beldiceanu, Nicolas and Lorca, Xavier},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {643-648},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-114},
  url       = {https://mlanthology.org/ijcai/2011/petit2011ijcai-generalized/}
}