Minimum Weight Tree Spanner Problem

Seja (G, w, t) uma tripla formada por um grafo conexo G = (V, E) com uma função peso w definida sobre E, e um número real t > 1. Uma árvore t-spanner de G é uma árvore geradora H de G tal que para quaisquer pares de vértices u, v, a distância entre u e v em H é no máximo t vezes a distância entre u e v em G. Estudamos o problema da árvore spanner de custo mínimo, denotado por MWTS (acrônimo de Minimum Weight Tree Spanner): dada uma tripla (G, w, t), encontrar em G uma árvore t-spanner que tenha o menor peso possível. Sabe-se que MWTS é NP-difícil para todo t ≥ 4, fixo. Propomos duas formulações lineares inteiras para o MWTS, baseadas em arborescências, de tamanho polinomial, e apresentamos resultados preliminares sobre os experimentos computacionais realizados com essas formulações.