Seminário de Teoria da Computação

                     Flávio Keidi Miyazawa


     Uma 2-aproximação para o projeto de redes resilientes

               Sexta-feira,  5 de novembro de 2004

                  Auditório (IC1), 13:00hs


Resumo:

Neste seminário iremos considerar um problema de projeto de redes com
certos requisitos de conectividade.  Dado uma função r:VxV->Z+,
dizemos que um grafo H satisfaz r se para todo par de vértices v e w
temos pelo menos r(v,w) caminhos aresta disjuntos em H.  Dado um grafo
G, com custos nas arestas, o objetivo é encontrar um subgrafo de custo
mínimo que satisfaz r. Um caso particular deste problema é o Problema
da Árvore de Steiner.  Apresentaremos um algoritmo 2-aproximado,
desenvolvido por Jain [1], e as idéias envolvidas na demonstração
deste fator.

[1] - K. Jain. A factor 2 approximation algorithm for the generalized
Steiner network design problem. Combinatorica, 21:39-60, 2001.