CHECKCOL: improved local search for graph coloring

DOI10.1016/J.JDA.2005.03.006MaRDI QIDQ2458929zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Massimiliano Caramia, Paolo Dell'Olmo, Giuseppe F. Italiano

Publication date 5 November 2007

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2005.03.006

zbMATH Keywords

combinatorial optimizationgraph coloringlocal searchtabu search

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Review text

CHECKCOL is a heuristic based on local search that colours the vertices of a graph. Computational experiments demonstrate that CHECKCOL outperforms the best previously known algorithms on four DIMACS benchmark graphs.

Recommendations

• Local optimization of colorings of graphs
• A survey of local search methods for graph coloring
• A Large Neighborhood Search Heuristic for Graph Coloring
• A search space ``cartography for guiding graph coloring heuristics
• scientific article; zbMATH DE number 4187836

Cites work

• An Introduction to Combinatorial Models of Dynamic Storage Allocation
• An introduction to timetabling
• Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths
• Genetic and hybrid algorithms for graph coloring
• Graph coloring with adaptive evolutionary algorithms
• scientific article; zbMATH DE number 978736 (Why is no real title available?)
• scientific article; zbMATH DE number 1062113 (Why is no real title available?)
• scientific article; zbMATH DE number 1128827 (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?)
• scientific article; zbMATH DE number 956855 (Why is no real title available?)
• On the hardness of approximating minimization problems
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• Register Allocation in Structured Programs
• Some experiments with simulated annealing for coloring graphs
• Some simplified NP-complete graph problems
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Using tabu search techniques for graph coloring

Cited in

(16)

• Combinatorial optimization in system configuration design
• COSINE: A new graph coloring algorithm
• Coloration neighbourhood search with forward checking
• A wide-ranging computational comparison of high-performance graph colouring algorithms
• An incremental search heuristic for coloring vertices of a graph
• Optimality clue for graph coloring problem
• Coloring graphs by iterated local search traversing feasible and infeasible solutions
• Embedding a novel objective function in a two-phased local search for robust vertex coloring
• Using an incomplete version of dynamic backtracking for graph colouring
• Solving the minimum-weighted coloring problem
• A new approach to the vertex coloring problem
• Intensification/diversification-driven ILS for a graph coloring problem
• A Large Neighborhood Search Heuristic for Graph Coloring
• Local optimization of colorings of graphs
• scientific article; zbMATH DE number 4127230 (Why is no real title available?)
• FWLS: a local search for graph coloring

Describes a project that uses

Uses Software

• Tabu search

This page was built for publication: CHECKCOL: improved local search for graph coloring

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