Optimal and Suboptimal Singleton Arc Consistency Algorithms
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 54-58.
Abstract
Singleton arc consistency (SAC) enhances the pruning capability of arc consistency by ensuring that the network cannot become arc inconsistent after the assignment of a value to a variable. Algorithms have already been proposed to enforce SAC, but they are far from optimal time complexity. We give a lower bound to the time complexity of enforcing SAC, and we propose an algorithm that achieves this complexity, thus being optimal. However, it can be costly in space on large problems. We then propose another SAC algorithm that trades time optimality for a better space complexity. Nevertheless, this last algorithm has a better worst-case time complexity than previously published SAC algorithms. An experimental study shows the good performance of the new algorithms.
@inproceedings{ijcai2005p28,
title = {Optimal and Suboptimal Singleton Arc Consistency Algorithms},
author = {Bessiere, Christian and Debruyne, Romuald},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {54--58},
year = {2005},
url = {https://ijcai.org/proceedings/2005/28},
}
TY - CPAPER TI - Optimal and Suboptimal Singleton Arc Consistency Algorithms AU - Bessiere, Christian AU - Debruyne, Romuald T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 54 EP - 58 UR - https://ijcai.org/proceedings/2005/28 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
