Cristina Gomes Fernandes (cris@ime.usp.br)
6a. feira - 31 de outubro - 14 horas
Sala 242--A
Resumo: Consideramos o problema do Subgrafo Planar Máximo: dado um grafo $G$, encontrar um subgrafo planar de $G$ maior possível. Dentre todos os algoritmos polinomiais conhecidos para esse problema NP-completo, nenhum tem uma prova de razão de aproximação maior que 1/3. Apresentamos o primeiro algoritmo de aproximação para o Subgrafo Planar Máximo cuja razão de aproximação é maior que 1/3: a razão é 4/9. Usamos o algoritmo também para encontrar "outerplanar subgraphs". Finalmente, mostramos que ambos o Subgrafo Planar Máximo e seu complemento, o problema de remover tão poucas arestas quando possível de forma que o que resta é um subgrafo planar, são Max SNP-difíceis.
Trabalho em conjunto com G. Calinescu, U. Finkler e H. Karloff.