Automatically Generated Algorithms for the Vertex Coloring Problem

Carlos Contreras Bolton, Gustavo Gatica, Víctor Parada

Resultado de la investigación: Article

4 Citas (Scopus)

Resumen

The vertex coloring problem is a classical problem in combinatorial optimization that consists of assigning a color to each vertex of a graph such that no adjacent vertices share the same color, minimizing the number of colors used. Despite the various practical applications that exist for this problem, its NP-hardness still represents a computational challenge. Some of the best computational results obtained for this problem are consequences of hybridizing the various known heuristics. Automatically revising the space constituted by combining these techniques to find the most adequate combination has received less attention. In this paper, we propose exploring the heuristics space for the vertex coloring problem using evolutionary algorithms. We automatically generate three new algorithms by combining elementary heuristics. To evaluate the new algorithms, a computational experiment was performed that allowed comparing them numerically with existing heuristics. The obtained algorithms present an average 29.97% relative error, while four other heuristics selected from the literature present a 59.73% error, considering 29 of the more difficult instances in the DIMACS benchmark.

Idioma originalEnglish
Número de artículoe58551
PublicaciónPLoS ONE
Volumen8
N.º3
DOI
EstadoPublished - 13 mar 2013

Huella dactilar

Coloring
Color
color
Combinatorial optimization
Evolutionary algorithms
system optimization
Benchmarking
Hardness
hardness
Heuristics
Experiments
methodology

ASJC Scopus subject areas

  • Medicine(all)
  • Biochemistry, Genetics and Molecular Biology(all)
  • Agricultural and Biological Sciences(all)

Citar esto

Contreras Bolton, Carlos ; Gatica, Gustavo ; Parada, Víctor. / Automatically Generated Algorithms for the Vertex Coloring Problem. En: PLoS ONE. 2013 ; Vol. 8, N.º 3.
@article{c0127db4adfa495cb50e664ccfc54312,
title = "Automatically Generated Algorithms for the Vertex Coloring Problem",
abstract = "The vertex coloring problem is a classical problem in combinatorial optimization that consists of assigning a color to each vertex of a graph such that no adjacent vertices share the same color, minimizing the number of colors used. Despite the various practical applications that exist for this problem, its NP-hardness still represents a computational challenge. Some of the best computational results obtained for this problem are consequences of hybridizing the various known heuristics. Automatically revising the space constituted by combining these techniques to find the most adequate combination has received less attention. In this paper, we propose exploring the heuristics space for the vertex coloring problem using evolutionary algorithms. We automatically generate three new algorithms by combining elementary heuristics. To evaluate the new algorithms, a computational experiment was performed that allowed comparing them numerically with existing heuristics. The obtained algorithms present an average 29.97{\%} relative error, while four other heuristics selected from the literature present a 59.73{\%} error, considering 29 of the more difficult instances in the DIMACS benchmark.",
author = "{Contreras Bolton}, Carlos and Gustavo Gatica and V{\'i}ctor Parada",
year = "2013",
month = "3",
day = "13",
doi = "10.1371/journal.pone.0058551",
language = "English",
volume = "8",
journal = "PLoS ONE",
issn = "1932-6203",
publisher = "Public Library of Science",
number = "3",

}

Automatically Generated Algorithms for the Vertex Coloring Problem. / Contreras Bolton, Carlos; Gatica, Gustavo; Parada, Víctor.

En: PLoS ONE, Vol. 8, N.º 3, e58551, 13.03.2013.

Resultado de la investigación: Article

TY - JOUR

T1 - Automatically Generated Algorithms for the Vertex Coloring Problem

AU - Contreras Bolton, Carlos

AU - Gatica, Gustavo

AU - Parada, Víctor

PY - 2013/3/13

Y1 - 2013/3/13

N2 - The vertex coloring problem is a classical problem in combinatorial optimization that consists of assigning a color to each vertex of a graph such that no adjacent vertices share the same color, minimizing the number of colors used. Despite the various practical applications that exist for this problem, its NP-hardness still represents a computational challenge. Some of the best computational results obtained for this problem are consequences of hybridizing the various known heuristics. Automatically revising the space constituted by combining these techniques to find the most adequate combination has received less attention. In this paper, we propose exploring the heuristics space for the vertex coloring problem using evolutionary algorithms. We automatically generate three new algorithms by combining elementary heuristics. To evaluate the new algorithms, a computational experiment was performed that allowed comparing them numerically with existing heuristics. The obtained algorithms present an average 29.97% relative error, while four other heuristics selected from the literature present a 59.73% error, considering 29 of the more difficult instances in the DIMACS benchmark.

AB - The vertex coloring problem is a classical problem in combinatorial optimization that consists of assigning a color to each vertex of a graph such that no adjacent vertices share the same color, minimizing the number of colors used. Despite the various practical applications that exist for this problem, its NP-hardness still represents a computational challenge. Some of the best computational results obtained for this problem are consequences of hybridizing the various known heuristics. Automatically revising the space constituted by combining these techniques to find the most adequate combination has received less attention. In this paper, we propose exploring the heuristics space for the vertex coloring problem using evolutionary algorithms. We automatically generate three new algorithms by combining elementary heuristics. To evaluate the new algorithms, a computational experiment was performed that allowed comparing them numerically with existing heuristics. The obtained algorithms present an average 29.97% relative error, while four other heuristics selected from the literature present a 59.73% error, considering 29 of the more difficult instances in the DIMACS benchmark.

UR - http://www.scopus.com/inward/record.url?scp=84874927047&partnerID=8YFLogxK

U2 - 10.1371/journal.pone.0058551

DO - 10.1371/journal.pone.0058551

M3 - Article

C2 - 23516506

AN - SCOPUS:84874927047

VL - 8

JO - PLoS ONE

JF - PLoS ONE

SN - 1932-6203

IS - 3

M1 - e58551

ER -