Automatically generated algorithms for the vertex coloring problem.

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 prob...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Carlos Contreras Bolton, Gustavo Gatica, Víctor Parada
Formato:	article
Lenguaje:	EN
Publicado:	Public Library of Science (PLoS) 2013
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/8879908b9fdf450fae305f0a5c8ae694
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:8879908b9fdf450fae305f0a5c8ae694
record_format	dspace
spelling	oai:doaj.org-article:8879908b9fdf450fae305f0a5c8ae6942021-11-18T07:53:37ZAutomatically generated algorithms for the vertex coloring problem.1932-620310.1371/journal.pone.0058551https://doaj.org/article/8879908b9fdf450fae305f0a5c8ae6942013-01-01T00:00:00Zhttps://www.ncbi.nlm.nih.gov/pmc/articles/pmid/23516506/?tool=EBIhttps://doaj.org/toc/1932-6203The 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.Carlos Contreras BoltonGustavo GaticaVíctor ParadaPublic Library of Science (PLoS)articleMedicineRScienceQENPLoS ONE, Vol 8, Iss 3, p e58551 (2013)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Carlos Contreras Bolton Gustavo Gatica Víctor Parada Automatically generated algorithms for the vertex coloring problem.
description	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.
format	article
author	Carlos Contreras Bolton Gustavo Gatica Víctor Parada
author_facet	Carlos Contreras Bolton Gustavo Gatica Víctor Parada
author_sort	Carlos Contreras Bolton
title	Automatically generated algorithms for the vertex coloring problem.
title_short	Automatically generated algorithms for the vertex coloring problem.
title_full	Automatically generated algorithms for the vertex coloring problem.
title_fullStr	Automatically generated algorithms for the vertex coloring problem.
title_full_unstemmed	Automatically generated algorithms for the vertex coloring problem.
title_sort	automatically generated algorithms for the vertex coloring problem.
publisher	Public Library of Science (PLoS)
publishDate	2013
url	https://doaj.org/article/8879908b9fdf450fae305f0a5c8ae694
work_keys_str_mv	AT carloscontrerasbolton automaticallygeneratedalgorithmsforthevertexcoloringproblem AT gustavogatica automaticallygeneratedalgorithmsforthevertexcoloringproblem AT victorparada automaticallygeneratedalgorithmsforthevertexcoloringproblem
_version_	1718422817311031296

Automatically generated algorithms for the vertex coloring problem.

Ejemplares similares