Embedding a novel objective function in a two-phased local search for robust vertex coloring

DOI10.1016/j.ejor.2007.01.063zbMath1205.05084MaRDI QIDQ2482807

Massimiliano Caramia, Paolo Dell'Olmo

Publication date: 24 April 2008

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2007.01.063

zbMATH Keywords

local search; benchmarks; vertex coloring; biased random sampling

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Combinatorial optimization in system configuration design

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using tabu search techniques for graph coloring
• Some experiments with simulated annealing for coloring graphs
• An introduction to timetabling
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Some simplified NP-complete graph problems
• Graph coloring with adaptive evolutionary algorithms
• Fast local search and guided local search and their application to British Telecom's workforce scheduling problem
• Genetic and hybrid algorithms for graph coloring
• Hybrid evolutionary algorithms for graph coloring
• CHECKCOL: improved local search for graph coloring
• Another look at graph coloring via propositional satisfiability
• Efficient algorithms for finding critical subgraphs
• A branch-and-cut algorithm for graph coloring
• An Introduction to Combinatorial Models of Dynamic Storage Allocation
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• A Pruning Procedure for Exact Graph Coloring
• The Complexity of Near-Optimal Graph Coloring
• New methods to color the vertices of a graph
• Register Allocation in Structured Programs
• A Column Generation Approach for Graph Coloring
• Iterative coloring extension of a maximum clique
• On the hardness of approximating minimization problems
• Finding the chromatic number by means of critical graphs
• Chromatic Scheduling and the Chromatic Number Problem
• Sur le coloriage des graphs
• Constraint propagation in graph coloring