Local optima topology for the k-coloring problem

DOI10.1016/0166-218X(94)90212-7MaRDI QIDQ1327233zbMATH OpenOpenAlexFDO

Authors Alain Hertz, Brigitte Jaumard, Marcus V. Poggi de Aragão

Publication date 18 July 1994

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(94)90212-7

zbMATH Keywords

\(k\)-coloringheuristicssimulated annealingtabu search

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Programming involving graphs or networks (90C35)

Recommendations

• The \(k\)-coloring fitness landscape
• A search space ``cartography for guiding graph coloring heuristics
• Local optimization of colorings of graphs
• On local search for the generalized graph coloring problem
• A survey of local search methods for graph coloring

Cites work

• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• An \(O(V^{5/3}E^{2/3})\) algorithm for the maximal flow problem
• scientific article; zbMATH DE number 3475221 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2166303 (Why is no real title available?)
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• Path Partitions in Directed Graphs
• Some experiments with simulated annealing for coloring graphs
• Tabu Search—Part I
• Tabu Search—Part II
• Using tabu search techniques for graph coloring

Cited in

(9)

• A search space ``cartography for guiding graph coloring heuristics
• Genetic algorithms and tabu search: Hybrids for optimization
• On local search for the generalized graph coloring problem
• Metaheuristics: A bibliography
• Optimality clue for graph coloring problem
• Constructive generation of very hard 3-colorability instances
• The \(k\)-coloring fitness landscape
• Variable neighborhood search: Principles and applications
• A cooperative search method for the \(k\)-coloring problem

This page was built for publication: Local optima topology for the \(k\)-coloring problem

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