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

DOI10.1016/J.DAM.2006.07.011MaRDI QIDQ2467347zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• On local search for the generalized graph coloring problem
• Coloring graphs by iterated local search traversing feasible and infeasible solutions
• A survey of local search methods for graph coloring
• Graph colorings with local constraints -- a survey
• Efficient constraint propagation for graph coloring
• Local optimization of colorings of graphs
• Constraint and satisfiability reasoning for graph coloring
• Exact solution of graph coloring problems via constraint programming and column generation
• The complexity of generalized graph colorings

Cites work

• scientific article; zbMATH DE number 1305705 (Why is no real title available?)
• scientific article; zbMATH DE number 2080324 (Why is no real title available?)
• scientific article; zbMATH DE number 956851 (Why is no real title available?)
• scientific article; zbMATH DE number 956853 (Why is no real title available?)
• scientific article; zbMATH DE number 956854 (Why is no real title available?)
• A Column Generation Approach for Graph Coloring
• A machine program for theorem-proving
• Another look at graph coloring via propositional satisfiability
• Coloration neighbourhood search with forward checking
• Combining the scalability of local search with the pruning techniques of systematic search
• Incomplete dynamic backtracking for linear pseudo-Boolean problems
• Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
• Negative effects of modeling techniques on search performance
• New methods to color the vertices of a graph
• On the parallel complexity of discrete relaxation in constraint satisfaction networks
• Symmetry Breaking and Local Search Spaces
• Theory and Applications of Satisfiability Testing

Cited in

(13)

• An evolutionary approach for bandwidth multicoloring problems
• Coloring graphs by iterated local search traversing feasible and infeasible solutions
• Exact solution of graph coloring problems via constraint programming and column generation
• A survey on vertex coloring problems
• A new approach to the vertex coloring problem
• CsegGraph: a graph colouring instance generator
• Graph coloring by multiagent fusion search
• Polyhedral studies for minimum‐span graph labelling with integer distance constraints
• Facet-inducing inequalities and a cut-and-branch for the bandwidth coloring polytope based on the orientation model
• Strong valid inequalities for Boolean logical pattern generation
• Hybrid metaheuristics for stochastic constraint programming
• An exact algorithm with learning for the graph coloring problem
• Coloration neighbourhood search with forward checking

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: Generalised graph colouring by a hybrid of local search and constraint programming

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