Automatically Generated Algorithms for the Vertex Coloring Problem

Vista sencilla de ítem
dc.contributor.authorContreras, C.
dc.contributor.authorGatica, G.
dc.contributor.authorParada, V.
dc.date.accessioned2023-05-15T17:24:57Z
dc.date.available2023-05-15T17:24:57Z
dc.date.issued2013
dc.descriptionIndexación: Scopus.es
dc.description.abstractThe 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.es
dc.description.urihttps://journals.plos.org/plosone/article?id=10.1371/journal.pone.0058551
dc.identifier.citationPLoS ONE, Volume 8, Issue 313, March 2013, Article number e58551es
dc.identifier.doi10.1371/journal.pone.0058551
dc.identifier.issn1932-6203
dc.identifier.urihttps://repositorio.unab.cl/xmlui/handle/ria/49631
dc.language.isoenes
dc.publisherPublic Library of Sciencees
dc.rights.licenseAttribution 4.0 International (CC BY 4.0)
dc.rights.urihttps://journals.plos.org/plosone/s/licenses-and-copyright
dc.subjectMetaheuristicses
dc.subjectChromatic Numberes
dc.subjectCombinatorial Optimization Problemes
dc.subjectautomationes
dc.subjectcalibrationes
dc.subjectclassification algorithmes
dc.subjectdata analysis softwarees
dc.subjectevolutionary algorithmes
dc.subjectmathematical analysises
dc.titleAutomatically Generated Algorithms for the Vertex Coloring Problemes
dc.typeArtículoes
Archivos
Bloque original
Mostrando 1 - 1 de 1
Miniatura
Nombre:
Contreras_Automatically Generated Algorithms for the Vertex Coloring Problem.pdf
Tamaño:
624.89 KB
Formato:
Adobe Portable Document Format
Descripción:
TEXTO COMPLETO EN INGLES
Descargar
Bloque de licencias
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
license.txt
Tamaño:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descripción:
Descargar
Colecciones
FIng - Artículos de Revista