A Fast Arc Consistency Algorithm for N-Ary Constraints
Abstract
The GAC-Scheme has become a popular general pur-pose algorithm for solving n-ary constraints, although it may scan an exponential number of supporting tuples. In this paper, we develop a major improvement of this scheme. When searching for a support, our new algo-rithm is able to skip over a number of tuples exponen-tial in the arity of the constraint by exploiting knowl-edge about the current domains of the variables. We demonstrate the effectiveness of the method for large table constraints.
Cite
Text
Lhomme and Régin. "A Fast Arc Consistency Algorithm for N-Ary Constraints." AAAI Conference on Artificial Intelligence, 2005.Markdown
[Lhomme and Régin. "A Fast Arc Consistency Algorithm for N-Ary Constraints." AAAI Conference on Artificial Intelligence, 2005.](https://mlanthology.org/aaai/2005/lhomme2005aaai-fast/)BibTeX
@inproceedings{lhomme2005aaai-fast,
title = {{A Fast Arc Consistency Algorithm for N-Ary Constraints}},
author = {Lhomme, Olivier and Régin, Jean-Charles},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2005},
pages = {405-410},
url = {https://mlanthology.org/aaai/2005/lhomme2005aaai-fast/}
}