Heurísticas para el problema de coloración robusta

Heurísticas para el problema de coloración robusta

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

Descripción completa

Detalles Bibliográficos
Autores principales: Gutiérrez-Andrade, Miguel Ángel, Lara-Velázquez, Pedro, Lopez-Bracho, Rafael, Ramírez-Rodríguez, Javier
Formato: Online
Idioma:spa
Publicado: Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2011
Acceso en línea:https://revistas.ucr.ac.cr/index.php/matematica/article/view/2119
id RMTA2119
record_format ojs
spelling RMTA21192022-01-26T17:33:35Z Heuristics for the robust coloring problem Heurísticas para el problema de coloración robusta Gutiérrez-Andrade, Miguel Ángel Lara-Velázquez, Pedro Lopez-Bracho, Rafael Ramírez-Rodríguez, Javier graph coloring robust coloring heuristics coloración de grafos coloración robusta heurísticas Let 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. Sean 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. Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2011-02-01 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Article application/pdf https://revistas.ucr.ac.cr/index.php/matematica/article/view/2119 10.15517/rmta.v18i1.2119 Revista de Matemática: Teoría y Aplicaciones; Vol. 18 No. 1 (2011): Revista de Matemática: Teoría y Aplicaciones; 137-148 Revista de Matemática: Teoría y Aplicaciones; Vol. 18 Núm. 1 (2011): Revista de Matemática: Teoría y Aplicaciones; 137-148 Revista de Matemática; Vol. 18 N.º 1 (2011): Revista de Matemática: Teoría y Aplicaciones; 137-148 2215-3373 1409-2433 spa https://revistas.ucr.ac.cr/index.php/matematica/article/view/2119/2082 Derechos de autor 2011 Revista de Matemática: Teoría y Aplicaciones
institution Universidad de Costa Rica
collection Revista de Matemática: Teoría y Aplicaciones
language spa
format Online
author Gutiérrez-Andrade, Miguel Ángel
Lara-Velázquez, Pedro
Lopez-Bracho, Rafael
Ramírez-Rodríguez, Javier
spellingShingle Gutiérrez-Andrade, Miguel Ángel
Lara-Velázquez, Pedro
Lopez-Bracho, Rafael
Ramírez-Rodríguez, Javier
Heurísticas para el problema de coloración robusta
author_facet Gutiérrez-Andrade, Miguel Ángel
Lara-Velázquez, Pedro
Lopez-Bracho, Rafael
Ramírez-Rodríguez, Javier
author_sort Gutiérrez-Andrade, Miguel Ángel
description Sean 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.
title Heurísticas para el problema de coloración robusta
title_short Heurísticas para el problema de coloración robusta
title_full Heurísticas para el problema de coloración robusta
title_fullStr Heurísticas para el problema de coloración robusta
title_full_unstemmed Heurísticas para el problema de coloración robusta
title_sort heurísticas para el problema de coloración robusta
title_alt Heuristics for the robust coloring problem
publisher Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate 2011
url https://revistas.ucr.ac.cr/index.php/matematica/article/view/2119
work_keys_str_mv AT gutierrezandrademiguelangel heuristicsfortherobustcoloringproblem
AT laravelazquezpedro heuristicsfortherobustcoloringproblem
AT lopezbrachorafael heuristicsfortherobustcoloringproblem
AT ramirezrodriguezjavier heuristicsfortherobustcoloringproblem
AT gutierrezandrademiguelangel heuristicasparaelproblemadecoloracionrobusta
AT laravelazquezpedro heuristicasparaelproblemadecoloracionrobusta
AT lopezbrachorafael heuristicasparaelproblemadecoloracionrobusta
AT ramirezrodriguezjavier heuristicasparaelproblemadecoloracionrobusta
_version_ 1811744086267265024

Ejemplares similares