Desempenho do algoritmo guloso na coloração de vértices em grafos de sistemas complexos

Abstract

In this work we aim to study the performance of greedy technique in the vertex coloring problem for graphs from Complex Systems. For doing that, twenty-five Complex Systems were selected, and from them we obtained the underlying graph on which the tests were performed. Two greedy heuristics for choosing the next vertex to be colored were analyzed: the first one uses the greatest degree heuristic for selecting the next vertex to be colored, and the second one applies the greatest saturation heuristic combined with the greatest degree heuristic. The results were compared with the optimal solution and some of the boundaries to the vertex coloring problem.