Solución a problemas de coloración clásicos utilizando Coloración de Gráficas Suaves
2016Profesores: Dr. Pedro Lara Velázquez y Dr. Miguel Ángel Gutiérrez Andrade
Resumen: La coloración de grafos es omnipresente en el modelado de aplicaciones del mundo real; por ejemplo, para mostrar asignación de frecuencias en problemas de telecomunicación; asignación de registros en un sistema operativo, programación de tareas; entre otras. La coloración de grafos se presenta en una gran variedad de formas de las cuales, la Coloración de Gráficas Suaves (CGS) es considerada una generalización del problema de coloración de gráficas. El problema de Coloración de Gráficas Suaves se ha utilizado recientemente en problemas de clasificación y de reconocimiento de patrones en general. En este problema tenemos que, dada una gráfica con ponderaciones en las aristas, el objetivo es encontrar una coloración que minimice la suma de las aristas con el mismo color en ambos extremos; es decir, la suma de las penalizaciones denominada dureza. Asimismo, existen otros parámetros importantes en la Coloración de Gráficas Suaves como lo son la solidez, la cual proporciona un valor promedio de las penalizaciones de la gráfica y resilencia que permite encontrar una cantidad adecuada de colores. Es sabido que este problema es del tipo NP-duro y es necesario el uso de metaheurísticas en instancias mayores a 20 vértices.
Objetivo general
- Desarrollar un algoritmo que resuelva varios problemas clásicos de coloración utilizando el enfoque de coloración de gráficas suaves
Objetivos específicos
- Realizar un estudio del estado del arte de los problemas de coloración clásicos, así como su representación como gráfica suave
- Compilación de instancias benchmark clásicas de cada uno de los problemas que se estudiarán
- Desarrollo de los algoritmos de solución
- Análisis de resultados y conclusiones
Ultima actualización 13/08/2022 por pcyti