Minimum Weight Tree Spanner Problem

  • Hugo Braga

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.

Publicado
06/07/2017
Como Citar

Selecione um Formato
BRAGA, Hugo. Minimum Weight Tree Spanner Problem. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 2. , 2017, São Paulo. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2017 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2017.3201.