Búsqueda dispersa para el problema de coloración de gráficas suaves - Vásquez Calderón, Hugo Eduardo (Universidad Autónoma Metropolitana, 2017)
El modelo de coloración de gráficas suaves es un caso particular del problema de coloración de gráficas, donde se busca una coloración que minimice la dureza de una gráfica completa con “n” vértices y los cuales están unidos por aristas con penalizaciones. El modelo de gráficas suaves ha probado que se puede resolver otros problemas de coloración, se ha utilizado como clasificador no supervisado, también para problemas de reconocimiento de patrones para comparar diferencias lingüísticas. Es un problema NP-Duro, por lo cual, para instancias mayores a 20 vértices, es necesario el uso de metaheurísticas para encontrar su solución. Es por esto que en esta investigación se desarrolla un algoritmo de búsqueda dispersa con la implementación de las mejores estrategias para cada uno de sus métodos, también se desarrolla instancias para poner aprueba el algoritmo y de esta formar corroborar las mejores estrategias a implementar. A su vez se compara con otras metaheurísticas para el problema de coloración robusta utilizado el modelo de coloración de gráficas suaves y nuestro algoritmo iguala las mejores soluciones obtenidas.