Using an incomplete version of dynamic backtracking for graph colouring

DOI10.1016/S1571-0653(04)00007-1MaRDI QIDQ2741266zbMATH OpenOpenAlexFDO

Authors Steven Prestwich

Publication date 23 September 2001

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s1571-0653(04)00007-1

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Recommendations

• Coloration neighbourhood search with forward checking
• A theoretical analysis of backtracking in the graph coloring problem
• Numerical experiences with graph coloring algorithms
• Efficient constraint propagation for graph coloring
• CHECKCOL: improved local search for graph coloring

Cites work

• A generic approach to combining stochastic algorithms with systematic constraint solvers
• Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis
• scientific article; zbMATH DE number 1149402 (Why is no real title available?)
• scientific article; zbMATH DE number 956851 (Why is no real title available?)
• Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems

Cited in

(6)

• A general-purpose hill-climbing method for order independent minimum grouping problems: A case study in graph colouring and bin packing
• Coloration neighbourhood search with forward checking
• A wide-ranging computational comparison of high-performance graph colouring algorithms
• Efficient constraint propagation for graph coloring
• A theoretical analysis of backtracking in the graph coloring problem
• Dynamic variable ordering in graph based backjumping algorithms for csps

This page was built for publication: Using an incomplete version of dynamic backtracking for graph colouring

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