Uma estratégia para selecionar vértices como candidatos a roteadores em uma árvore de Steiner

  • João Guilherme Martinez
  • Rosiane de Freitas
  • Altigran da Silva
  • Fábio Protti
DOI: https://doi.org/10.5753/etc.2018.3171

Resumo


O problema da árvore de Steiner em grafos é NP-difícil, no entanto, algoritmos que fazem uso de heurísticas conseguem obter resultados próximos da solução ótima em tempo polinomial. Neste trabalho apresentamos um novo algoritmo baseado em um algoritmo exato enumerativo da literatura. A heurística proposta seleciona vértices como candidatos a serem roteadores naárvore de Steiner.

Publicado
26/07/2018
Como Citar

Selecione um Formato
MARTINEZ, João Guilherme; DE FREITAS, Rosiane; DA SILVA, Altigran; PROTTI, Fábio. Uma estratégia para selecionar vértices como candidatos a roteadores em uma árvore de Steiner. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3171.