Application of Biased Random-key Genetic Algorithm and Formulations for the Grundy Number Problem and the Connected Grundy Number Problem

Nome do aluno

Mateus Carvalho da Silva

Título do trabalho

Application of biased random-key genetic algorithm and formulations for the Grundy number problem and the connected Grundy number problem

Resumo do trabalho

Given a graph G, its Grundy number Γ(G), defines the worst-case behavior for the well-
known and widely used first-fit greedy coloring heuristic. Specifically, Γ(G) is the largest k for which a k-coloring can be obtained with the first-fit heuristic. The connected Grundy number Γc(G) gives the worst-case behavior for the first-fit coloring heuristic connected, that is, one in which each vertex to be colored, except the first, is added adjacent to an already colored vertex, both problems are NP-hard. In this master’s thesis, we present heuristic and exact approaches to Grundy coloring and the connected Grundy coloring problem, which are optimization problems consisting of obtaining the Grundy number and the connected Grundy number, respectively. This study proposes the use of the algorithm Biased Random-Key Genetic Algorithm (BRKGA) and formulations by representatives and integer programming. A new combinatorial upper bound is also proposed that is valid for both problems and can be computed using dynamic programming. The computational experiments show that our new upper bound can improve over a well-established combinatorial bound available in the literature for several instances. The results also evidence that the formulation by representatives has an overall superior performance than the standard formulation, achieving better results for the denser instances, while the latter
performs better for the sparser ones to the Grundy number problem. However, we show that
this type of formulations with integer programming are computationally impractical for the
connected version. Furthermore, the BRKGA can find high-quality solutions for both problems and can be used with confidence in large instances where the formulations fail for the Grundy number problem.

Orientador

Rafael Augusto de Melo

Co-orientador (opcional)

Márcio Costa Santos

Membro Titular Externo (com afiliação)

Maurício Guilherme de Carvalho Resende

Link para o curriculum lattes

https://scholar.google.com.br/citations?user=KTmPx50AAAAJ&hl=pt-BR

Membro Titular Interno ou Titular Externo 2 (com afiliação)

Pedro Henrique Gonzáles Silva

Link para o curriculum lattes

http://lattes.cnpq.br/5349830056087028

Membro Suplente Externo (com afiliação)

Jesus Ossian da Cunha Silva

Link para o curriculum lattes

http://lattes.cnpq.br/4282182643218971

Membro Suplente Interno ou Suplente Externo 2 (com afiliação)

Frederico Araujo Durão

Link para o curriculum lattes

http://lattes.cnpq.br/6271096128174325

Data da defesa

13 Dec, 2023

Horário da defesa

3:00 PM