Backtracking through biconnected components of a constraint graph
Jean-François Baget, Yannic Tognetti · International Joint Conference on Artificial Intelligence · 2001
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.