José Augusto Soares
IME-USP
Sexta-feira, 14 de maio de 2004, 14:00
Sala 267, Bloco A, IME-USP
Resumo:
Dado um grafo G com custos associados às suas arestas e um subconjunto R de seus vértices, uma árvore de Steiner é uma árvore que conecta todos os vértices de R. Os vértices de R são chamados de vértices terminais.
O problema de Steiner consiste em encontrar uma árvore de Steiner de custo mínimo. O problema abordado neste seminário é o de encontrar uma árvore de Steiner de custo mínimo na qual cada vértice terminal é uma folha. Os dois problemas são NP-difíceis.
Vamos comentar sobre algoritmos de aproximação para os problemas, destacando o caso em que os custos das arestas são 1 ou 2. O algoritmo de aproximação a ser apresentado foi desenvolvido por Fábio Viduani Martinez, José Coelho e eu.