A search space ``cartography for guiding graph coloring heuristics

DOI10.1016/j.cor.2009.06.024zbMath1176.90613OpenAlexW1988405740MaRDI QIDQ1040976

Pascale Kuntz, Jin-Kao Hao, Daniel Cosmin Porumbel

Publication date: 27 November 2009

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

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

zbMATH Keywords

graph coloringlocal optima distributionsearch by learning

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Coloring of graphs and hypergraphs (05C15)

Related Items

A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations ⋮ Iterated maxima search for the maximally diverse grouping problem ⋮ An exact algorithm with learning for the graph coloring problem ⋮ Multi-restart iterative search for the pickup and delivery traveling salesman problem with FIFO loading ⋮ Neighborhood decomposition-driven variable neighborhood search for capacitated clustering ⋮ An opposition-based memetic algorithm for the maximum quasi-clique problem ⋮ Responsive strategic oscillation for solving the disjunctively constrained knapsack problem ⋮ Coloring large graphs based on independent set extraction ⋮ 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 memetic algorithm for graph coloring ⋮ INFORMED REACTIVE TABU SEARCH FOR GRAPH COLORING ⋮ AN EXTRACTION AND EXPANSION APPROACH FOR GRAPH COLORING

Uses Software

• DIMACS
• Tabu search

Cites Work

• 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
• A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding
• Variable space search for graph coloring
• Local optima topology for the \(k\)-coloring problem
• A variable neighborhood search for graph coloring.
• Partition-distance: A problem and class of perfect graphs arising in clustering
• Graph coloring for air traffic flow management
• Genetic and hybrid algorithms for graph coloring
• 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
• A survey of local search methods for graph coloring
• Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis
• A Metaheuristic Approach for the Vertex Coloring Problem
• A Large Neighborhood Search Heuristic for Graph Coloring
• A graph coloring algorithm for large scheduling problems
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• New methods to color the vertices of a graph
• 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
• Chromatic Scheduling and the Chromatic Number Problem
• Frozen development in graph coloring