Un algoritmo novedoso de búsqueda con retroceso para coloreo por listas

Abstract

Dado un grafo, el problema de coloreo por listas consiste en asignar a cada nodo un color que pertenezca a una lista predeterminada de colores válidos para ese nodo, de modo que vértices adyacentes no reciban un mismo color y usando la mínima cantidad de colores. Este problema es una generalización del problema de coloreo y es NP-difícil incluso para grafos de intervalos [1]. Un enfoque que puede tomarse al tratar de resolver problemas NP-difíciles es diseñar algoritmos de búsqueda con retroceso. En [2], la búsqueda con retroceso se define como “una forma sistemática de iterar por todas las posibles configuraciones del espacio de búsqueda”. Con el fin de evitar un gran esfuerzo computacional al realizar una búsqueda exhaustiva, es fundamental poder aplicar podas que permitan descartar soluciones parciales cuando no pueden ser extendidas a soluciones completas mejores que la mejor encontrada hasta el momento. Además, la eficiencia de estos algoritmos depende fuertemente de las formas en las que se extienden las soluciones en cada paso. En este trabajo proponemos un novedoso algoritmo de búsqueda por retroceso que emplea distintas estrategias inteligentes para explorar el espacio de búsqueda para resolver el problema de coloreo por listas para grafos generales y presentamos los resultados computacionales obtenidos.