Búsqueda dispersa para el problema de coloración de gráficas suaves
2016Profesores: Dr. Pedro Lara Velázquez y Dr. Sergio Gerardo de los Cobos Silva
Resumen: El problema de coloración de gráficas suaves es una generalización del problema de coloración, en donde un grafo completo, las aristas tienen penalizaciones. Este problema se ha demostrado que puede resolver otros problemas tales como coloración mínima, coloración equitativa, entre otros; y en tiempos recientes, como parte de un trabajo de tesis de maestría, se ha demostrado su utilidad como clasificador no supervisado. Debido a que este modelo es del tipo NP-difícil, se requiere el uso de metaheurísticas para problemas con mas de 20 vértices. En este proyecto se propone realizar un algoritmo de solución utilizando la metaheurística de búsqueda dispersa.
Objetivo general
- Desarrollar un algoritmo de solución para el problema de coloración de gráficas suaves utilizando la técnica metaheurística de búsqueda dispersa
Objetivos específicos
- Revisión del estado del arte de problema a resolver y la técnica de solución
- Planteamiento de instancias apropiadas para verificar la calidad del algoritmo
- Propuesta de un algoritmo de solución
- Implementación del algoritmo en C, FreeBASIC o Python, y su validación en las instancias de prueba seleccionadas anteriormente
- Redacción de la idónea comunicación de resultados
Ultima actualización 13/08/2022 por pcyti