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.




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


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


Pedro Henrique Gonzáles Silva


Link para o curriculum lattes


Membro Suplente Externo (com afiliação)


Jesus Ossian da Cunha Silva


Link para o curriculum lattes


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


Frederico Araujo Durão


Link para o curriculum lattes


Data da defesa


13 Dec, 2023


Horário da defesa


3:00 PM



Data da Defesa: 
13/12/2023 - 15:00
Tipo de Defesa: 
Defesa de Mestrado