Una comparación de modelos para un nuevo problema de coloreo

Abstract

El problema de coloreo de vértices consiste en asignar un color a cada vértice de un grafo tal que vértices adyacentes reciban colores distintos, utilizando la mínima cantidad de colores. Este problema ha sido ampliamente estudiado. En este trabajo, presentamos un problema al que llamamos “Problema de Coloreo de Vértices por Componentes Conexas” (CCCP, por sus siglas en inglés), que es una variación del problema de coloreo de vértices y que, hasta donde sabemos, no ha sido definido ni estudiado previamente. Después de demostrar varias propiedades, formalizamos su definición con 3 modelos de programación matemática. Obtenemos también cotas inferiores y superiores, que nos permiten eliminar variables de los modelos originales. Además, diseñamos varias heurísticas para CCCP que permiten obtener soluciones iniciales. Para comparar los rendimientos de los algoritmos basados en los modelos propuestos, tanto respecto a la calidad de las soluciones encontradas así como a los tiempos de ejecución, generamos un conjunto de instancias y llevamos a cabo experimentación. Las conclusiones nos permiten comprender qué partes del algoritmo deberíamos mejorar y también concebir nuevas formas de tratar nuestro problema.