Backtracking Through Biconnected Components of a Constraint Graph
Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 291-295.
Abstract
The algorithm presented here, BCC, is an enhancement of the well known Backtrack used to solve constraint satisfaction problems. Though most backtrack improvements rely on propagation of local informations, BCC uses global knowledge of the constraint graph structure (and in particular its biconnected components) to reduce search space, permanently removing values and compiling partial solutions during exploration. This algorithm performs well by itself, without any filtering, when the biconnected components are small, achieving optimal time complexity in case of a tree. Otherwise, it remains compatible with most existing techniques, adding only a negligible overhead cost.
@inproceedings{ijcai2001p41,
title = {Backtracking Through Biconnected Components of a Constraint Graph},
author = {Baget, Jean-François and Tognetti, Yannic S.},
booktitle = {Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, {IJCAI-01}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {291--295},
year = {2001},
url = {https://ijcai.org/proceedings/2001/41},
}
TY - CPAPER TI - Backtracking Through Biconnected Components of a Constraint Graph AU - Baget, Jean-François AU - Tognetti, Yannic S. T2 - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01 PB - International Joint Conferences on Artificial Intelligence PY - 2001 SP - 291 EP - 295 UR - https://ijcai.org/proceedings/2001/41 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
