On edge orienting methods for graph coloring

DOI10.1007/s10878-006-9019-3zbMath1124.05033OpenAlexW2141410486MaRDI QIDQ2385485

Bernard Gendron, Patrick St-Louis, Alain Hertz

Publication date: 12 October 2007

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-006-9019-3

zbMATH Keywords

Local searchGraph coloringEdge orienting

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Very Large-Scale Neighborhood Search: Overview and Case Studies on Coloring Problems, Parameterized mixed graph coloring, Variable space search for graph coloring, A wide-ranging computational comparison of high-performance graph colouring algorithms, Corrigendum to ``Variable space search for graph coloring [Discrete Appl. Math. 156, No.\,13, 2551--2560 (2008; Zbl 1213.05085)]

Uses Software

• DIMACS
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two novel evolutionary formulations of the graph coloring problem
• A survey of local search methods for graph coloring
• Job Shop Scheduling by Simulated Annealing
• A Column Generation Approach for Graph Coloring
• Finding the chromatic number by means of critical graphs
• Nombre chromatique et plus longs chemins d'un graphe
• Chromatic Scheduling and the Chromatic Number Problem