Determining if (FC-) (conflict-directed) backjumping visits a given node is NP-hard

DOI10.1016/S0004-3702(01)00146-1zbMath0983.68179OpenAlexW2026185565MaRDI QIDQ5958710

Bernd S. W. Schröder

Publication date: 3 March 2002

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0004-3702(01)00146-1

zbMATH Keywords

constraint satisfactionbackjumpingbacktrackingconflict-directed backjumpingforward checkingmaintaining arc consistency

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (1)

Chaos for implicit difference equations with snap-back repellers

Cites Work

• Exploiting the deep structure of constraint problems
• A theoretical evaluation of selected backtracking algorithms.
• Locating the phase transition in binary constraint satisfaction problems
• Heuristic Sampling: A Method for Predicting the Performance of Tree Searching Programs
• Estimating the Efficiency of Backtrack Programs
• Tree Size by Partial Backtracking
• Unnamed Item
• Unnamed Item

This page was built for publication: Determining if (FC-) (conflict-directed) backjumping visits a given node is NP-hard