Refining the Basic Constraint Propagation Algorithm
Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 309-314.
Abstract
Propagating constraints is the main feature of any constraint solver. This is thus of prime importance to manage constraint propagation as efficiently as possible, justifying the use of the best algorithms. But the ease of integration is also one of the concerns when implementing an algorithm in a constraint solver. This paper focuses on AC-3, which is the simplest arc consistency algorithm known so far. We propose two refinements that preserve as much as possible the ease of integration into a solver (no heavy data structure to be maintained during search), while giving some noticeable improvements in efficiency. One of the proposed refinements is analytically compared to AC-6, showing interesting properties, such as optimality of its worst-case time complexity.
@inproceedings{ijcai2001p44,
title = {Refining the Basic Constraint Propagation Algorithm},
author = {Bessiere, Christian and Régin, Jean-Charles},
booktitle = {Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, {IJCAI-01}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {309--314},
year = {2001},
url = {https://ijcai.org/proceedings/2001/44},
}
TY - CPAPER TI - Refining the Basic Constraint Propagation Algorithm AU - Bessiere, Christian AU - Régin, Jean-Charles T2 - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01 PB - International Joint Conferences on Artificial Intelligence PY - 2001 SP - 309 EP - 314 UR - https://ijcai.org/proceedings/2001/44 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
