---
title: "Backtracking Through Biconnected Components of a Constraint Graph"
authors:
  - "Jean-François Baget"
  - "Yannic S. Tognetti"
doi: ""
url: "https://ijcai.org/proceedings/2001/41"
pdf: "https://ijcai.org/proceedings/2001/0041.pdf"
venue: "Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence"
year: 2001
pages: "291-295"
track: ""
keywords:
---

# Backtracking Through Biconnected Components of a Constraint Graph

Jean-François Baget, Yannic S. Tognetti

*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.