Cristina Gomes Fernandes
IME-USP
Sexta-feira, 23 de agosto de 2002, 14:30
Sala 268, Bloco A, IME-USP
Resumo: O problema de Steiner em grafos (PSG) consiste no seguinte: dado um grafo com comprimento nas arestas e um conjunto R de vértices - os vértices terminais, encontrar uma árvore no grafo que contenha todos os vértices terminais e tenha comprimento mínimo.
O problema de Steiner em grafos é NP-difícil. Os algoritmos de aproximação que atingem as melhores razões de aproximação conhecidas até o momento para o PSG utilizam as chamadas árvores k-restritas. Vários destes algoritmos seguem um certo padrão. Neste seminário, descreveremos esse padrão, mostraremos quatro algoritmos que seguem esse padrão e analisaremos um deles: o algoritmo do ganho relativo, projetado por Zelikovsky.
O algoritmo do ganho relativo atinge uma razão de aproximação de 1,694 para o PSG. Ele não é o melhor algoritmo de aproximação conhecido para o PSG, porém, dentre os algoritmos apresentados, é o que tem uma análise mais simples. A melhor razão de aproximação conhecida para o PSG é de 1,55 e é atingida pelo algoritmo de Robins e Zelikovsky, que será um dos algoritmos descritos no seminário.
Se houver tempo, discutiremos brevemente uma generalização do PSG e uma aplicação em biologia computacional em que estamos interessados.