A survey of local search methods for graph coloring

DOI10.1016/j.cor.2005.07.028zbMath1086.90060MaRDI QIDQ2489304

Alain Hertz, Philippe Galinier

Publication date: 16 May 2006

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2005.07.028

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

Related Items

A supernodal formulation of vertex colouring with applications in course timetabling, Graph colouring approaches for a satellite range scheduling problem, A cooperative search method for the \(k\)-coloring problem, A sequential elimination algorithm for computing bounds on the clique number of a graph, Variable space search for graph coloring, About equivalent interval colorings of weighted graphs, Variable neighbourhood search: methods and applications, An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring, Combinatorial optimization in system configuration design, Variable neighbourhood search: Methods and applications, Graph coloring by multiagent fusion search, A search space ``cartography for guiding graph coloring heuristics, On a parallel genetic-tabu search based algorithm for solving the graph colouring problem, A memetic algorithm for graph coloring, On edge orienting methods for graph coloring, Efficient algorithms for finding critical subgraphs, An adaptive memory algorithm for the \(k\)-coloring problem

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Optimization by Simulated Annealing
• Using tabu search techniques for graph coloring
• Some experiments with simulated annealing for coloring graphs
• An introduction to timetabling
• STABULUS: A technique for finding stable sets in large graphs with tabu search
• Variable neighborhood search
• A variable neighborhood search for graph coloring.
• Genetic algorithm for graph coloring: exploration of Galinier and Hao's algorithm
• Future paths for integer programming and links to artificial intelligence
• Genetic and hybrid algorithms for graph coloring
• Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs
• Probabilistic diversification and intensification in local search for vehicle routing
• Hybrid evolutionary algorithms for graph coloring
• An adaptive memory algorithm for the \(k\)-coloring problem
• A graph coloring algorithm for large scheduling problems
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• Tabu Search—Part I
• An application of graph coloring to printed circuit testing
• New methods to color the vertices of a graph