Un algoritmo híbrido para el problema de coloración robusta de gráficas

Un algoritmo híbrido para el problema de coloración robusta de gráficas

En este artículo se propone un algoritmo híbrido que combina técnicas de programación matemática (algoritmo de Kruskal y la estrategia de mantener consistencia de arcos para resolver el problema de satisfacción de restricciones) y métodos heurísticos (método de composición musical y DSATUR) para res...

Descripción completa

Detalles Bibliográficos
Autores principales: Mora-Gutiérrez, Román Anselmo, Ramírez-Rodríguez, Javier, Rincón-García, Eric A., Ponsich, Antonin, Laureano-Cruces, Ana Lilia
Formato: Online
Idioma:eng
Publicado: Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2016
Acceso en línea:https://revistas.ucr.ac.cr/index.php/matematica/article/view/25269
id RMTA25269
record_format ojs
spelling RMTA252692022-01-31T17:42:17Z A hybrid algorithm for the robust graph coloring problem Un algoritmo híbrido para el problema de coloración robusta de gráficas Mora-Gutiérrez, Román Anselmo Ramírez-Rodríguez, Javier Rincón-García, Eric A. Ponsich, Antonin Laureano-Cruces, Ana Lilia metaheuristics combinatorial optimization integer programming metaheurísticas optimización combinatoria programación entera A hybridalgorithm which combines mathematical programming techniques (Kruskal’s algorithm and the strategy of maintaining arc consistency to solve constraint satisfaction problem “CSP”) and heuristic methods (musical composition method and DSATUR) to resolve the robust graph coloring problem (RGCP) is proposed in this paper. Experimental result shows that this algorithm is better than the other algorithms presented on the literature. En este artículo se propone un algoritmo híbrido que combina técnicas de programación matemática (algoritmo de Kruskal y la estrategia de mantener consistencia de arcos para resolver el problema de satisfacción de restricciones) y métodos heurísticos (método de composición musical y DSATUR) para resolver el problema de coloración robusta de gráficas (RGCP). Resultados experimentales muestran que este algorimo da mejores resultados que otros presentados en la literatura. Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2016-08-04 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Article application/pdf https://revistas.ucr.ac.cr/index.php/matematica/article/view/25269 10.15517/rmta.v23i2.25269 Revista de Matemática: Teoría y Aplicaciones; Vol. 23 No. 2 (2016): Revista de Matemática: Teoría y Aplicaciones; 421-444 Revista de Matemática: Teoría y Aplicaciones; Vol. 23 Núm. 2 (2016): Revista de Matemática: Teoría y Aplicaciones; 421-444 Revista de Matemática; Vol. 23 N.º 2 (2016): Revista de Matemática: Teoría y Aplicaciones; 421-444 2215-3373 1409-2433 eng https://revistas.ucr.ac.cr/index.php/matematica/article/view/25269/26432 Derechos de autor 2016 omán Anselmo Mora-Gutiérrez, Javier Ramírez-Rodríguez, Eric A. Rincón-García, Antonin Ponsich, Ana Lilia Laureano-Cruces https://creativecommons.org/licenses/by-nc-sa/4.0
institution Universidad de Costa Rica
collection Revista de Matemática: Teoría y Aplicaciones
language eng
format Online
author Mora-Gutiérrez, Román Anselmo
Ramírez-Rodríguez, Javier
Rincón-García, Eric A.
Ponsich, Antonin
Laureano-Cruces, Ana Lilia
spellingShingle Mora-Gutiérrez, Román Anselmo
Ramírez-Rodríguez, Javier
Rincón-García, Eric A.
Ponsich, Antonin
Laureano-Cruces, Ana Lilia
Un algoritmo híbrido para el problema de coloración robusta de gráficas
author_facet Mora-Gutiérrez, Román Anselmo
Ramírez-Rodríguez, Javier
Rincón-García, Eric A.
Ponsich, Antonin
Laureano-Cruces, Ana Lilia
author_sort Mora-Gutiérrez, Román Anselmo
description En este artículo se propone un algoritmo híbrido que combina técnicas de programación matemática (algoritmo de Kruskal y la estrategia de mantener consistencia de arcos para resolver el problema de satisfacción de restricciones) y métodos heurísticos (método de composición musical y DSATUR) para resolver el problema de coloración robusta de gráficas (RGCP). Resultados experimentales muestran que este algorimo da mejores resultados que otros presentados en la literatura.
title Un algoritmo híbrido para el problema de coloración robusta de gráficas
title_short Un algoritmo híbrido para el problema de coloración robusta de gráficas
title_full Un algoritmo híbrido para el problema de coloración robusta de gráficas
title_fullStr Un algoritmo híbrido para el problema de coloración robusta de gráficas
title_full_unstemmed Un algoritmo híbrido para el problema de coloración robusta de gráficas
title_sort un algoritmo híbrido para el problema de coloración robusta de gráficas
title_alt A hybrid algorithm for the robust graph coloring problem
publisher Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate 2016
url https://revistas.ucr.ac.cr/index.php/matematica/article/view/25269
work_keys_str_mv AT moragutierrezromananselmo ahybridalgorithmfortherobustgraphcoloringproblem
AT ramirezrodriguezjavier ahybridalgorithmfortherobustgraphcoloringproblem
AT rincongarciaerica ahybridalgorithmfortherobustgraphcoloringproblem
AT ponsichantonin ahybridalgorithmfortherobustgraphcoloringproblem
AT laureanocrucesanalilia ahybridalgorithmfortherobustgraphcoloringproblem
AT moragutierrezromananselmo unalgoritmohibridoparaelproblemadecoloracionrobustadegraficas
AT ramirezrodriguezjavier unalgoritmohibridoparaelproblemadecoloracionrobustadegraficas
AT rincongarciaerica unalgoritmohibridoparaelproblemadecoloracionrobustadegraficas
AT ponsichantonin unalgoritmohibridoparaelproblemadecoloracionrobustadegraficas
AT laureanocrucesanalilia unalgoritmohibridoparaelproblemadecoloracionrobustadegraficas
AT moragutierrezromananselmo hybridalgorithmfortherobustgraphcoloringproblem
AT ramirezrodriguezjavier hybridalgorithmfortherobustgraphcoloringproblem
AT rincongarciaerica hybridalgorithmfortherobustgraphcoloringproblem
AT ponsichantonin hybridalgorithmfortherobustgraphcoloringproblem
AT laureanocrucesanalilia hybridalgorithmfortherobustgraphcoloringproblem
_version_ 1811744095965544448

Ejemplares similares