Hybrid backtracking bounded by tree-decomposition of constraint networks

DOI10.1016/S0004-3702(02)00400-9MaRDI QIDQ814455zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Bounded backtracking for the valued constraint satisfaction problems
• Tree decomposition method combined with separator in constraint satisfaction problems
• A theoretical evaluation of selected backtracking algorithms.
• A comparison of structural CSP decomposition methods
• Combining restarts, nogoods and bag-connected decompositions for solving csps

Cites work

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

Cited in

(15)

• AND/OR search spaces for graphical models
• Combining restarts, nogoods and bag-connected decompositions for solving 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
• Sufficient and necessary conditions for solution finding in valuation-based systems
• On the adaptive control of a class of SISO dynamic hybrid systems
• Computing partial hypergraphs of bounded width
• Generalized hypertree decomposition for solving non binary CSP with compressed table constraints
• Tree decomposition method combined with separator in constraint satisfaction problems
• Dynamic Management of Heuristics for Solving Structured CSPs
• A sufficient condition for backtrack-bounded search
• Combining restarts, nogoods and decompositions for solving CSPs
• Bounded backtracking for the valued constraint satisfaction problems
• Constraint reasoning

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q814455)