Formulação matemática para o problema da árvore t-spanner de custo mínimo - Sousa, Gabriel H. de; Campêlo, Manoel (Anais do Encontro de Teoria da Computação (ETC); 2023: Anais do VIII Encontro de Teoria da Computação, 2023)
O Problema da Árvore t-Spanner de Custo Mínimo, cuja entrada é um grafo simples G, ponderado em arestas, e um parâmetro t ≥ 1, consiste em determinar uma árvore geradora T de G de menor custo dentre aquelas onde a distância entre qualquer par de vértices i e j em T é no máximo t vezes o menor peso de um caminho entre i e j em G. Propomos uma formulação matemática que pode ser derivada pela projeção de uma formulação já existente. Implementamos ambos os modelos e comparamos seus desempenhos computacionais.