Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/65411
Title in Portuguese: Algoritmos para o problema do número de Grundy
Author: Florencio, Davi Gomes
Advisor(s): Tavares, Wladimir Araújo
Keywords: Teoria dos grafos
Coloração de grafos
Número Grundy
Algoritmos
Issue Date: 2022
Citation: FLORENCIO, Davi Gomes. Algoritmos para o problema do número de Grundy. 2022. 75 f. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação)-Universidade Federal do Ceará, Campus de Quixadá, Quixadá, 2022.
Abstract in Portuguese: No presente trabalho, estudamos o Problema do Número de Grundy que consiste em determinar a maior quantidades de cores que o Algoritmo Guloso de Coloração consegue atribuir a um grafo. Este algoritmo tem o seguinte princípio geral: receber, um a um, os vértices do grafo a ser colorido, atribuindo sempre a menor cor possível a este vértice. O maior número de cores utilizados pelo Algoritmo Guloso de Coloração é chamado de número de Grundy ou número cromático guloso do grafo. Sabe-se que determinar o número de Grundy de um grafo qualquer pertence à classe NP-completo. O objetivo deste trabalho foi propor novas soluções exatas para o Problema do Número de Grundy. Neste trabalho, foram propostos um limite inferior e um superior, ambos baseados em heurísticas gulosas. Com relação às soluções exatas, foram propostas um algoritmo de Programação Dinâmica, um algoritmo Branch and Bound e três formulações de Programação Linear Inteira. Foram geradas instâncias aleatórias e da classe Stacked Book, no qual foram realizados diversos testes computacionais.
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.
URI: http://www.repositorio.ufc.br/handle/riufc/65411
metadata.dc.type: TCC
Appears in Collections:CIÊNCIA DA COMPUTAÇÃO-QUIXADÁ - Monografias

Files in This Item:
File Description SizeFormat 
2021_tcc_dgflorencio.pdf675,71 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.