Banca de DEFESA: MATEUS CARVALHO DA SILVA

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
STUDENT : MATEUS CARVALHO DA SILVA
DATE: 13/12/2023
TIME: 15:00
LOCAL: Online
TITLE:

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

KEY WORDS:

combinatorial optimization; graph coloring; Grundy number; BRKGA; worst-case
analysis.

PAGES: 49
BIG AREA: Ciências Exatas e da Terra
AREA: Ciência da Computação
SUMMARY:

Given a graph G, its Grundy number $\Gamma(G)$ defines the worst-case behavior for the well-known and widely used first-fit greedy coloring heuristic. Specifically, $\Gamma(G)$ is the largest $k$ for which a $k$-coloring can be obtained with the first-fit heuristic. The connected Grundy number $\Gamma_c(G)$ gives the worst-case behavior for the connected first-fit coloring heuristic, 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 the Grundy coloring problem 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 a algorithm Biased Random-Key Genetic Algorithm (BRKGA) and the use of integer programming formulations using a more traditional (standard) approach and a representative one. A new combinatorial upper bound is also proposed that is valid for both problems and an algorithm using dynamic programming for its calculation. The computational experiments show that the 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 coloring problem. However, we show that these types of integer programming formulations 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 coloring problem.

COMMITTEE MEMBERS:
Presidente - 2115562 - RAFAEL AUGUSTO DE MELO
Interno - 2011187 - FREDERICO ARAUJO DURAO
Externo à Instituição - PEDRO HENRIQUE GONZÁLEZ SILVA - UFRJ
Externo à Instituição - MAURICIO GUILHERME DE CARVALHO RESENDE