A HYBRID ALGORITHM FOR THE ROBUST GRAPH COLORING PROBLEM

 

Authors
Mora Gutiérrez, Román Anselmo; Ramírez Rodríguez, Javier; Rincón García, Eric A.; Ponsich, Antonin; Laureano Cruces, Ana Lilia
Format
Article
Status
publishedVersion
Description

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.

Publication Year
2016
Language
eng
Topic
metaheuristics
combinatorial optimization
integer programming
05C15
metaheurísticas
optimización combinatoria
programación entera
05C15
Fuente
Portal de Revistas UCR
Get full text
https://revistas.ucr.ac.cr/index.php/matematica/article/view/25269
Derechos
openAccess
Licencia
Derechos de autor 2016 Revista de Matemática: Teoría y Aplicaciones