Implementação e análise de algoritmos para coloração de arestas

Abstract

The Edge Coloring Problem, extensively studied in Graph Theory, concerns coloring the edges of a graph such that edges incident on the same vertex have distinct colors and the number of used colors is minimized. The most important result on the edge coloring problem was proposed in 1964 with Vizing's Theorem, which established that the minimum number of colors needed to color a graph, the chromatic index X, is limited between the values square and triangle + 1, where triangle is the maximum degree of the graph. This work presents two efficient edge coloring implementations for simple graphs based on Vizing's Theorem using no more than ? + 1 colors. Several adaptations in data structures and in the processing order of edges and colors have been proposed in order to reduce the runtime of the operations more frequently performed. We also developed two preprocessing strategies that provide a partially colored graph as input to the edge coloring algorithm. Experimental results show that the proposed strategies allow gains up to 63.92% in terms of performance in the edge coloring algorithms studied here.