1985/10/01 by Eugene C. Freuder · 1 citation
Computer Science · Mathematics · #Constraint Satisfaction and Optimization #Data Management and Algorithms #AI-based Problem Solving and Planning #Backtracking #Constraint satisfaction problem #Constraint satisfaction #Constraint graph #Computer science #Constraint learning #Bounded function #Constraint (computer-aided design) #Graph #Upper and lower bounds #Branch and bound #Mathematics #Mathematical optimization #Search tree #Local consistency #Theoretical computer science #Search algorithm #Artificial intelligence
paper · pdf · doi:10.1145/4221.4225
openalex publication_date 1985/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/18
Backtrack search is often used to solve constraint satisfaction problems. A relationship involving the structure of the constraints is described that provides a bound on the backtracking required to advance deeper into the backtrack tree. This analysis leads to upper bounds on the effort required for solution of a class of constraint satisfaction problems. The solutions involve a combination of relaxation preprocessing and backtrack search. The bounds are expressed in terms of the structure of the constraint connections. Specifically, the effort is shown to have a bound exponential in the size of the largest biconnected component of the constraint graph, as opposed to the size of the graph as a whole.