An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring

DOI10.1016/j.cor.2010.01.015zbMath1188.90269OpenAlexW2118944864MaRDI QIDQ976050

Pascale Kuntz, Daniel Cosmin Porumbel, Jin-Kao Hao

Publication date: 11 June 2010

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

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

zbMATH Keywords

graph coloringpopulation managementdiversity controlmemetic and hybrid algorithmmulti-parent crossover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Learning and adaptive systems in artificial intelligence (68T05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A multi-parent genetic algorithm for the quadratic assignment problem ⋮ Hybrid evolutionary search for the minimum sum coloring problem of graphs ⋮ Reinforcement learning based tabu search for the minimum load coloring problem ⋮ A memetic algorithm for the minimum sum coloring problem ⋮ Dynamic Programming Driven Memetic Search for the Steiner Tree Problem with Revenues, Budget, and Hop Constraints ⋮ Memetic search for the max-bisection problem ⋮ A systematic study on meta-heuristic approaches for solving the graph coloring problem ⋮ A two-phase tabu-evolutionary algorithm for the 0-1 multidimensional knapsack problem ⋮ Maximum-weight stable sets and safe lower bounds for graph coloring ⋮ Quantum annealing of the graph coloring problem ⋮ Safe Lower Bounds for Graph Coloring ⋮ A wide-ranging computational comparison of high-performance graph colouring algorithms ⋮ Coloring large graphs based on independent set extraction ⋮ An effective heuristic algorithm for sum coloring of graphs ⋮ Improving the extraction and expansion method for large graph coloring ⋮ INFORMED REACTIVE TABU SEARCH FOR GRAPH COLORING ⋮ AN EXTRACTION AND EXPANSION APPROACH FOR GRAPH COLORING ⋮ A hybrid metaheuristic method for the maximum diversity problem

Uses Software

• Mathematica
• DIMACS
• Tabu search

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
• Variable space search for graph coloring
• A search space ``cartography for guiding graph coloring heuristics
• A memetic algorithm for graph coloring
• A variable neighborhood search for graph coloring.
• Partition-distance: A problem and class of perfect graphs arising in clustering
• Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs
• The algebra of genetic algorithms
• Hybrid evolutionary algorithms for graph coloring
• A graph coloring heuristic using partial solutions and a reactive tabu scheme
• An adaptive memory algorithm for the \(k\)-coloring problem
• An evolutionary approach for bandwidth multicoloring problems
• A survey of local search methods for graph coloring
• \(\text{MA}\mid\text{PM}\): memetic algorithms with population management
• A Metaheuristic Approach for the Vertex Coloring Problem
• A survey on vertex coloring problems
• A Large Neighborhood Search Heuristic for Graph Coloring
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• Feature Article—Genetic Algorithms for the Operations Researcher
• A procedure for the strategic planning of locations, capacities and districting of jails: application to Chile
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• An algorithm for the chromatic number of a graph