Backtracking Through Biconnected Components of a Constraint Graph
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.
Cite
Text
Baget and Tognetti. "Backtracking Through Biconnected Components of a Constraint Graph." International Joint Conference on Artificial Intelligence, 2001.Markdown
[Baget and Tognetti. "Backtracking Through Biconnected Components of a Constraint Graph." International Joint Conference on Artificial Intelligence, 2001.](https://mlanthology.org/ijcai/2001/baget2001ijcai-backtracking/)BibTeX
@inproceedings{baget2001ijcai-backtracking,
title = {{Backtracking Through Biconnected Components of a Constraint Graph}},
author = {Baget, Jean-François and Tognetti, Yannic S.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2001},
pages = {291-296},
url = {https://mlanthology.org/ijcai/2001/baget2001ijcai-backtracking/}
}