Formulações matemáticas para o problema da árvore t-spanner de custo mínimo

Vol 55, 2023 - 161074
Trabalho completo (oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

No Problema da Árvore $t$-Spanner de Custo Mínimo, cuja entrada é um grafo $G=(V,E)$ ponderado e $t\geq 1$ um parâmetro, denominado de fator de dilatação, o objetivo consiste em determinar uma árvore geradora $T$ em $G$ de menor custo, tal que a distância entre qualquer par de vértices $i$ e $j$ na árvore $T$ é no máximo $t$ vezes a distância entre $i$ e $j$ em $G$. Neste trabalho, estudamos e propomos aperfeiçoamentos para duas formulações matemáticas da literatura. Implementamos ambos os modelos e comparamos seus desempenhos computacionais com outros métodos exatos da 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 do Ceará
Eixo Temático
  • 15. PM – Programação Matemática
Palavras-chave
Árvore t-Spanner de Custo Mínimo; árvore geradora; Formulação Matemática