Explorando os Limites de Heurísticas Construtivas para o Problema da Árvore Geradora com Número Mínimo de Ramificações

Vol 55, 2023 - 160589
Trabalho completo (oral)
Favoritar este trabalho
Como citar esse trabalho?
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 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 quatro novas heurísticas construtivas para o problema, inspiradas no Algoritmo de Prim: dois métodos gulosos e duas variantes randomizadas. Os resultados obtidos para as instâncias de referência se mostraram superiores aos anteriormente encontrados na literatura.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade Federal Fluminense
  • 2 UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO
Eixo Temático
  • 19. TAG – Teoria e Algoritmos em Grafos
Palavras-chave
árvore geradora; Grafos; Ramificações