Algoritmos exatos para o problema de coloração de grafos

Abstract

In this work we present some of the main strategies to reduce the time from the Backtracking algorithm for coloring graphs. In the Backtracking algorithm we can change the branching strategy and the lower and upper bounds that are used by the original algorithm. Two coloring algorithms, BTSL and BTDSATUR, are presented, which were elaborated from some changes in the Backtracking algorithm. In these changes proposals are presented for the Backtracking branching strategy: static form based on the ordering SL and dynamic form based on the DSATUR algorithm. With regard to the upper limit, it will be indicated by the number of colors used by the sequential coloring algorithm, with order based on the SL order for the BTSL, and the number of colors used by the DSATUR coloring algorithm, in the case of the BTDSATUR algorithm. In addition, a new algorithm will be proposed for this graph coloring problem, the BTH, that will be a hybrid algorithm that will combine the two algorithms (BTSL and BTDSATUR), dividing a percentage of vertices that will be colored by each algorithm. Finally, we provide a algorithm performance analysis based on the time and number of nodes generated for each input graph in the experiments that were proposed. From the experiments, we can notice that the proposed strategy used, despite being better than the BTSL algorithm, does not overcome DSATUR.