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.
Referências
Bondy, J. A. (1989). Trigraphs. Discrete Math., 75(1-3):69–79.
Cai, L. and Corneil, D. G. (1995). Tree spanners. SIAM J. Disc. Math., 8(3):359–387.
Miller, C. E., Tucker, A. W., and Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. J. ACM, 7(4):326–329.
Peleg, D. and Upfal, E. (1988). A tradeoff between space and efficiency for routing tables. In STOC ’88, pages 43–52, New York, USA.
