An adaptive memory algorithm for the \(k\)-coloring problem

DOI10.1016/j.dam.2006.07.017zbMath1131.05089OpenAlexW2092998591MaRDI QIDQ2467362

Alain Hertz, Nicolas Zufferey, Philippe Galinier

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

zbMATH Keywords

tabu searchgraph coloringadaptive memory algorithmshybrid evolutionary heuristics

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Graph colouring approaches for a satellite range scheduling problem, Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm, An exact algorithm with learning for the graph coloring problem, A parallel adaptive memory algorithm for the capacitated modular hub location problem, Heuristics for a project management problem with incompatibility and assignment costs, An exact approach for the vertex coloring problem, Quantum annealing of the graph coloring problem, Metaheuristics for truck loading in the car production industry, A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems, A branch-and-price algorithm for the robust graph coloring problem, A cooperative search method for the \(k\)-coloring problem, A graph coloring heuristic using partial solutions and a reactive tabu scheme, Graph Coloring Models and Metaheuristics for Packing Applications, A survey on vertex coloring problems, Efficient algorithms for finding critical subgraphs, Variable space search for graph coloring, Hybrid evolutionary algorithm for the b-chromatic number, Consistent neighborhood search for combinatorial optimization, A wide-ranging computational comparison of high-performance graph colouring algorithms, Coloring large graphs based on independent set extraction, A survey of local search methods for graph coloring, An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring, Improving the extraction and expansion method for large graph coloring, A NEW APPROACH TO THE VERTEX COLORING PROBLEM, Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach, CsegGraph: a graph colouring instance generator, Graph coloring by multiagent fusion search, A search space ``cartography for guiding graph coloring heuristics, A memetic algorithm for graph coloring, INFORMED REACTIVE TABU SEARCH FOR GRAPH COLORING, AN EXTRACTION AND EXPANSION APPROACH FOR GRAPH COLORING

Uses Software

• DIMACS

Cites Work

• Using tabu search techniques for graph coloring
• Some experiments with simulated annealing for coloring graphs
• A framework for the description of evolutionary algorithms
• 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
• A survey of local search methods for graph coloring
• A taxonomy of evolutionary algorithms in combinatorial optimization
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• New methods to color the vertices of a graph
• Chromatic Scheduling and the Chromatic Number Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item