Hybrid backtracking bounded by tree-decomposition of constraint networks

DOI10.1016/S0004-3702(02)00400-9zbMath1082.68803OpenAlexW2138319640MaRDI QIDQ814455

Philippe Jégou, Cyril Terrioux

Publication date: 7 February 2006

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

Full work available at URL: https://doi.org/10.1016/s0004-3702(02)00400-9

zbMATH Keywords

Constraint networksEmpirical evaluationHybrid algorithmsTime-spaceTree-decomposition

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (10)

Computing partial hypergraphs of bounded width ⋮ Combining restarts, nogoods and bag-connected decompositions for solving csps ⋮ Dynamic Management of Heuristics for Solving Structured CSPs ⋮ Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms ⋮ Subproblem ordering heuristics for AND/OR best-first search ⋮ Combining CP and ILP in a tree decomposition of bounded height for the sum colouring problem ⋮ On the adaptive control of a class of SISO dynamic hybrid systems ⋮ Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints ⋮ Sufficient and necessary conditions for solution finding in valuation-based systems ⋮ AND/OR search spaces for graphical models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tree clustering for constraint networks
• Consistency in networks of relations
• Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis
• Radio link frequency assignment
• An optimal backtrack algorithm for tree-structured constraint satisfaction problems
• A theoretical evaluation of selected backtracking algorithms.
• A comparison of structural CSP decomposition methods
• Networks of constraints: Fundamental properties and applications to picture processing
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• A Sufficient Condition for Backtrack-Free Search
• Algorithmic Aspects of Vertex Elimination on Graphs
• A sufficiently fast algorithm for finding close to optimal clique trees
• Topological parameters for time-space tradeoff

This page was built for publication: Hybrid backtracking bounded by tree-decomposition of constraint networks