Optimal and Suboptimal Singleton Arc Consistency Algorithms
Abstract
Singleton arc consistency (SAC) is a local consistency that ensures that a constraint network can be made arc consistent after any assignment of a value to a variable. A first contribution of this paper is to show experimentally that the optimal-time algorithm proposed in [5] (which was analyzed only theoretically) is efficient in practice compared to previous SAC algorithms. However, it can be costly in space on large problems, even with the small improvements we propose at the beginning of this paper. To reduce this space consumption, we propose another SAC algorithm requiring less space but no longer optimal in time. An experimental study on random problems highlights the good performance of this second algorithm.
Cite
Text
Bessiere and Debruyne. "Optimal and Suboptimal Singleton Arc Consistency Algorithms." International Joint Conference on Artificial Intelligence, 2005.Markdown
[Bessiere and Debruyne. "Optimal and Suboptimal Singleton Arc Consistency Algorithms." International Joint Conference on Artificial Intelligence, 2005.](https://mlanthology.org/ijcai/2005/bessiere2005ijcai-optimal/)BibTeX
@inproceedings{bessiere2005ijcai-optimal,
title = {{Optimal and Suboptimal Singleton Arc Consistency Algorithms}},
author = {Bessiere, Christian and Debruyne, Romuald},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2005},
pages = {54-59},
url = {https://mlanthology.org/ijcai/2005/bessiere2005ijcai-optimal/}
}