Fast heuristics for the edge coloring of large graphs

Autor:	Rolf Drechsler, M. Hilgemeier, Nicole Drechsler
Rok vydání:	2003
Předmět:	Combinatorics Greedy coloring Edge coloring Mathematical optimization Indifference graph Chordal graph Computer science Simulated annealing Graph coloring Heuristics 1-planar graph MathematicsofComputing_DISCRETEMATHEMATICS
Zdroj:	DSD Scopus-Elsevier
DOI:	10.1109/dsd.2003.1231932
Popis:	Heuristic algorithms for coloring the edges of large undirected single-edge graphs with (or very close to) the minimal number of colors are presented. Compared to simulated annealing and a grouping genetic algorithm for small graphs, the heuristics were not only faster by orders of magnitude, but almost all solutions had the optimal color number; the rest differed by at most two colors. For large graphs, the heuristics were validated by an evolutionary algorithm. Here, the heuristics often found an optimum or a solution very close to it.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e19d47261bace369b2cec2b8390acf78 https://doi.org/10.1109/dsd.2003.1231932 Zobrazit plný text záznamu