Algoritmos enumerativos para o problema da b-coloração e aplicações relacionadas

Abstract

A b-coloring of a graph G with k colors, is a proper coloring of the vertices of G, in such a way that in every color class there is a vertex adjacent to all other k − 1 colors classes, such vertex is called b-vertex. In this paper is proposed an enumerative algorithm for the b-coloring problem, which lists all viable solutions for the problem and an algorithm that finds the b-cromatic number of a graph using prunning techniques. Some algorithms often give only the optimal or one viable solution, and that solution may be not capable to solve the problem. With all the solutions found, there is no need to search for other ways to find just one another solution. Both algorithms were tested with graphs using the DIMACS pattern, and they showed to be very effective. The tests were peformed using graphs with five different densities, and they were executed on both algorithms. The algorithm responsable to find the b-cromatic number, which is the same as the full enumeration but uses prunning, had its time reduced drasticaly, showing that the prunning techniques are effective.