Cristina Gomes Fernandes (cris@ime.usp.br)
6a. feira - 21 de novembro - 14 horas
Sala 242--A
Resumo: Consideraremos o Problema do Subgrafo Planar de Peso Máximo: dado um grafo G com peso nas arestas, encontrar um subgrafo planar de G de peso máximo. Sabe-se que o Problema do Subgrafo Planar de Peso Máximo é NP-difícil. Nenhum algoritmo previamente conhecido para o Subgrafo Planar de Peso Máximo tinha razão de performance maior que 1/3, que é obtida por um algoritmo que produz uma árvore geradora de G de peso máximo. Apresentaremos o primeiro algoritmo com uma razão de aproximação maior que 1/3 para o problema. Baseado no algoritmo para árvores de Steiner de Berman-Ramaiyer, o novo algoritmo tem razão de performance pelo menos 1/3 + 1/72. Também mostramos que se G é completo e os pesos nas arestas satisfazem a desigualdade triangular, então a razão de performance é pelo menos 3/8.
Trabalho em conjunto com G. Calinescu, H. Karloff e A. Zelikovsky.