Heuristics for the robust coloring problem

Heurísticas para el problema de coloración robusta

dc.creatorGutiérrez-Andrade, Miguel Ángel
dc.creatorLara-Velázquez, Pedro
dc.creatorLopez-Bracho, Rafael
dc.creatorRamírez-Rodríguez, Javier
dc.date2011-02-01
dc.date.accessioned2023-08-03T16:18:39Z
dc.date.available2023-08-03T16:18:39Z
dc.identifierhttps://revistas.ucr.ac.cr/index.php/matematica/article/view/2119
dc.identifier10.15517/rmta.v18i1.2119
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/7886670
dc.descriptionLet G and Ḡ be complementary graphs. Given a penalty function defined on the edges of Ḡ, we will say that the rigidity of a k-coloring of G is the sum of the penalties of the edges of Ḡ joining vertices of the same color. Based on the previous definition, the Robust Coloring Problem (RCP) is stated as the search of the minimum rigidity k-coloring. In this work a comparison of heuristics based on simulated annealing, GRASP and scatter search is presented. These are the best results for the RCP that have been obtained.en-US
dc.descriptionSean G y Ḡ dos grafos complementarios. Dada una función de penalización en las aristas de Ḡ, la rigidez de una k-coloración de G se define como la suma de las penalizaciones en las aristas de Ḡ cuyos vértices incidentes son del mismo color. Con base en la definición anterior, el Problema de Coloración Robusta (PCR) se define como la búsqueda de la k-coloración de rigidez mı́nima. Este trabajo realiza un estudio comparativo de varias técnicas heurísticas: Recocido Simulado, GRASP, y Búsqueda Dispersa. Los resultados aquí presentados son los mejores obtenidos para el PCR.es-ES
dc.formatapplication/pdf
dc.languagespa
dc.publisherUniversidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)es-ES
dc.relationhttps://revistas.ucr.ac.cr/index.php/matematica/article/view/2119/2082
dc.rightsDerechos de autor 2011 Revista de Matemática: Teoría y Aplicacioneses-ES
dc.sourceRevista de Matemática: Teoría y Aplicaciones; Vol. 18 No. 1 (2011): Revista de Matemática: Teoría y Aplicaciones; 137-148en-US
dc.sourceRevista de Matemática: Teoría y Aplicaciones; Vol. 18 Núm. 1 (2011): Revista de Matemática: Teoría y Aplicaciones; 137-148es-ES
dc.sourceRevista de Matemática; Vol. 18 N.º 1 (2011): Revista de Matemática: Teoría y Aplicaciones; 137-148pt-PT
dc.source2215-3373
dc.source1409-2433
dc.subjectgraph coloringen-US
dc.subjectrobust coloringen-US
dc.subjectheuristicsen-US
dc.subjectcoloración de grafoses-ES
dc.subjectcoloración robustaes-ES
dc.subjectheurísticases-ES
dc.titleHeuristics for the robust coloring problemen-US
dc.titleHeurísticas para el problema de coloración robustaes-ES
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:eu-repo/semantics/publishedVersion
dc.typeArticlees-ES


Este ítem pertenece a la siguiente institución