Coloring graphs by iterated local search traversing feasible and infeasible solutions

DOI10.1016/J.DAM.2006.07.013MaRDI QIDQ2467355zbMATH OpenOpenAlexFDO

Authors Massimiliano Caramia, Paolo Dell'Olmo

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.013

zbMATH Keywords

heuristicslocal searchvertex coloringgraph coloring benchmarks

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15)

Recommendations

• scientific article; zbMATH DE number 2079895
• A survey of local search methods for graph coloring
• On local search for the generalized graph coloring problem
• Generalised graph colouring by a hybrid of local search and constraint programming
• Local optimization of colorings of graphs
• Analysis of an iterated local search algorithm for vertex coloring
• CHECKCOL: improved local search for graph coloring
• Iterated local search with tabu search for the weighted vertex coloring problem
• Feasible Graphs and Colorings

Cites work

• scientific article; zbMATH DE number 3503127 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1128827 (Why is no real title available?)
• scientific article; zbMATH DE number 1488073 (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?)
• A Column Generation Approach for Graph Coloring
• A Pruning Procedure for Exact Graph Coloring
• A branch-and-cut algorithm for graph coloring
• A graph coloring algorithm for large scheduling problems
• An Introduction to Combinatorial Models of Dynamic Storage Allocation
• An introduction to timetabling
• Another look at graph coloring via propositional satisfiability
• CHECKCOL: improved local search for graph coloring
• Chromatic Scheduling and the Chromatic Number Problem
• Constraint propagation in graph coloring
• Efficient algorithms for finding critical subgraphs
• Finding the chromatic number by means of critical graphs
• Genetic and hybrid algorithms for graph coloring
• Graph coloring with adaptive evolutionary algorithms
• Hybrid evolutionary algorithms for graph coloring
• Iterative coloring extension of a maximum clique
• New methods to color the vertices of a graph
• 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
• Sur le coloriage des graphs
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Using tabu search techniques for graph coloring

Cited in

(15)

• Population-based iterated greedy algorithm for the S-labeling problem
• Generalised graph colouring by a hybrid of local search and constraint programming
• A priority-based genetic algorithm for a flexible job shop scheduling problem
• Intensification/diversification-driven ILS for a graph coloring problem
• Expected polynomial-time randomized algorithm for graph coloring problem
• Three new upper bounds on the chromatic number
• A new approach to the vertex coloring problem
• Combinatorial optimization in system configuration design
• scientific article; zbMATH DE number 2079895 (Why is no real title available?)
• CsegGraph: a graph colouring instance generator
• Strong valid inequalities for Boolean logical pattern generation
• Analysis of an iterated local search algorithm for vertex coloring
• An incremental search heuristic for coloring vertices of a graph
• Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
• An exact algorithm with learning for the graph coloring problem

This page was built for publication: Coloring graphs by iterated local search traversing feasible and infeasible solutions

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