ML Anthology

Data Structures for Generalised Arc Consistency for Extensional Constraints

Ian P. Gent, Christopher Jefferson, Ian Miguel, Peter Nightingale
AAAI 2007 pp. 191-197
/aaai/2007/gent2007aaai-data/

Abstract

Extensional (table) constraints are an important tool for attacking combinatorial problems with constraint programming. Recently there has been renewed interest in fast propagation algorithms for these constraints. We describe the use of two alternative data structures for maintaining generalised arc consistency on extensional constraints. The first, the Next-Difference list, is novel and has been developed with this application in mind. The second, the trie, is well known but its use in this context is novel. Empirical analyses demonstrate the efficiency of the resulting approaches, both in GACschema, and in the watched-literal table constraint in Minion.

PDF AAAI Semantic Scholar

Cite

Text

Gent et al. "Data Structures for Generalised Arc Consistency for Extensional Constraints." AAAI Conference on Artificial Intelligence, 2007.

Markdown

[Gent et al. "Data Structures for Generalised Arc Consistency for Extensional Constraints." AAAI Conference on Artificial Intelligence, 2007.](https://mlanthology.org/aaai/2007/gent2007aaai-data/)

BibTeX

@inproceedings{gent2007aaai-data,
  title     = {{Data Structures for Generalised Arc Consistency for Extensional Constraints}},
  author    = {Gent, Ian P. and Jefferson, Christopher and Miguel, Ian and Nightingale, Peter},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2007},
  pages     = {191-197},
  url       = {https://mlanthology.org/aaai/2007/gent2007aaai-data/}
}