Algoritmos para o problema do número de Grundy

Abstract

In the present work, we study the Grundy Number Problem, which consists of determining the largest amount of colors that the Greedy Coloring Algorithm can assign to a graph. This algorithm has the following general principle: receive, one by one, the vertices of the graph to be colored, always attributing the smallest possible color to this vertex. The largest number of colors used by the Greedy Coloring Algorithm is called the Grundy number or greedy chromatic number of the graph. It is known that determining the Grundy number of any graph belongs to the NP-complete class. The objective of this work was to propose new exact solutions to the Grundy Number Problem. In this work, a lower and an upper bound were proposed, both based on greedy heuristics. Regarding the exact solutions, a Dynamic Programming algorithm, a Branch and Bound algorithm and three Integer Linear Programming formulations were proposed. Random instances and the Stacked Book class were generated, in which several computational tests were performed.