Show simple item record

Un Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta

dc.creatorLara Velázquez, Pedro
dc.creatorGutiérrez Andrade, Miguel Ángel
dc.creatorRamírez Rodríguez, Javier
dc.creatorLópez Bracho, Rafael
dc.date.accessioned2015-05-19T18:43:00Z
dc.date.available2015-05-19T18:43:00Z
dc.date.issued2012-03-22 00:00:00
dc.identifier.citationhttp://revistas.ucr.ac.cr/index.php/matematica/article/view/255
dc.identifier.issn
dc.identifier.urihttp://hdl.handle.net/10669/12901
dc.description.abstractLet G and \bar{G} be two complementary graphs. Given a penalty function defined over the edges of \bar{G}, it is said that the rigidity of a k-coloring of G is the summation ofthe penalties of the edges of G that join vertices whose endpoint are equally colored. Based on this previous definition, the Robust Coloring Problem is set when searching the valid k-coloring of minimum rigidity. Yáñez and Ramírez proved that this is an NP-hard problem. In this work we present an evolutive algorithm based in the scatter search technique, which obtains optimal solutions for those instances for which an optimal solution is known, and obtains the best known solutions compared to other heuristics, such as: simulated annealing, tabu search and partial enumeration.
dc.description.abstractSean G y bar{G} un par de gráficas complementarias. Dada una función de peso definida sobre las aristas de \bar{G}, se dice que la rigidez de una k-coloración válida de G es la suma de los pesos de las aristas de \bar{G} que unen vértices del mismo color. Con base en la anterior definición, se plantea el Problema de Coloración Robusta al buscar la k-coloración válida de rigidez mínima. Yáñez y Ramírez probaron que este problema es NP-duro. En este trabajo se presenta un algoritmo evolutivo basado en la técnica de búsqueda dispersa, la cual obtiene soluciones óptimas, en las instancias para las que se conoce la solución óptima, y obtiene las mejores soluciones conocidas comparadas con otras heurísticas, tales como: recocido simulado, búsqueda tabú y enumeración parcial.
dc.format.extent111-120
dc.relation.ispartofRevista de Matemática: Teoría y Aplicaciones Vol. 12 Núm. 1-2 2012
dc.titleUn Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta
dc.titleUn Algoritmo Evolutivo para Resolver el Problema de Coloración Robusta
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:eu-repo/semantics/publishedVersion
dc.date.updated2015-05-19T18:43:00Z
dc.language.rfc3066es
dc.identifier.doi10.15517/rmta.v12i1-2.255


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record