Defesa de Dissertação de Mestrado de Anderson Beltrão de Oliveira, em 27/10/2023, às 10:00 horas, na sala 310 do Instituto de Computação e por videoconferência
Link para defesa: https://meet.google.com/epy-myna-ntc
Heurísticas Gulosas e Randomizadas para o Problema da Árvore Geradora com Número Mínimo de Ramificações
Resumo:
O problema conhecido na literatura como “Minimum Branch Vertices Problem” (MBV) consiste em encontrar uma árvore geradora T de um grafo não direcionado G que contenha o menor número de vértices com grau maior ou igual a três em T, chamados de ramificações ou “branch vertices”. O MBV é NP-difícil, e, por esta razão, muitas abordagens heurísticas têm sido propostas para contornar sua complexidade computacional. Neste trabalho propomos oito novas heurísticas construtivas para o problema, inspiradas no Algoritmo de Prim: quatro métodos gulosos e quatro variantes randomizadas. Os resultados obtidos para as instâncias de referência se mostraram superiores aos métodos construtivos anteriormente encontrados na literatura.
Abstract:
The Minimum Branch Vertices Problem (MBV) aims at finding a spanning tree T of an undirected graph G that minimizes the number of vertices with a degree greater than or equal to three in T, known as branch vertices. The MBV is NP-hard, and for this reason many heuristic approaches have been proposed to deal with its computational complexity. This study proposes eight novel constructive heuristics for the problem, inspired by Prim’s Algorithm: four greedy methods and four randomized variations. The results obtained for the reference instances proved to be superior to the construction methods previously found in the literature.
Banca examinadora:
Prof. Fábio Protti, UFF – Presidente
Profa. Simone de Lima Martins, UFF
Prof. Rodrigo Lamblet Mafort, UERJ
Profa. Maria Claudia Silva Boeres, UFES