Minimum Weight Tree Spanner Problem
Resumo
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.