Generalised graph colouring by a hybrid of local search and constraint programming

DOI10.1016/j.dam.2006.07.011zbMath1179.90312OpenAlexW2070048232MaRDI QIDQ2467347

Steven Prestwich

Publication date: 21 January 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.07.011

zbMATH Keywords

constraint programmingforward checkinggeneralised graph colouringhybrid local search

Mathematics Subject Classification ID

Nonlinear programming (90C30) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

An exact algorithm with learning for the graph coloring problem, Strong valid inequalities for Boolean logical pattern generation, Facet-inducing inequalities and a cut-and-branch for the bandwidth coloring polytope based on the orientation model, A survey on vertex coloring problems, An evolutionary approach for bandwidth multicoloring problems, Polyhedral studies for minimum‐span graph labelling with integer distance constraints, A NEW APPROACH TO THE VERTEX COLORING PROBLEM, Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation, Hybrid metaheuristics for stochastic constraint programming

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
• Coloration neighbourhood search with forward checking
• Combining the scalability of local search with the pruning techniques of systematic search
• Negative effects of modeling techniques on search performance
• Incomplete dynamic backtracking for linear pseudo-Boolean problems
• Another look at graph coloring via propositional satisfiability
• On the parallel complexity of discrete relaxation in constraint satisfaction networks
• New methods to color the vertices of a graph
• A Column Generation Approach for Graph Coloring
• Theory and Applications of Satisfiability Testing
• Symmetry Breaking and Local Search Spaces
• A machine program for theorem-proving