Cristina Gomes Fernandes (cris@ime.usp.br)
6a. feira - 10 de outubro - 14 horas
Sala 242--A
Resumo: O problema dos Multicortes pode ser definido da seguinte forma: dado um grafo $G$ e uma coleção de pares $s_i, t_i$ de vértices distintos de $G$, encontrar um conjunto mínimo de arestas de $G$ cuja remoção desconecta cada $s_i$ do $t_i$ correspondente. Sabe-se que o problema dos Multicortes é NP-difícil e Max SNP-difícil mesmo quando a entrada é restrita a ser uma árvore. Para árvores em geral, o problema dos Multicortes é pelo menos tão difícil quanto o problema de Cobertura de Vértices e a melhor razão de aproximação conhecida é dois. Nós apresentamos um esquema de aproximação polinomial para o problema dos Multicortes para árvores de grau limitado, isto é, para todos $\eps > 0$, um algoritmo de aproximação com razão $(1+\eps)$ para árvores de grau limitado. O algoritmo pode ser implementado em tempo linear. Além disso, mostraremos que o problema continua NP-difícil para árvores binárias.
Esse trabalho é conjunto com Gruia Calinescu (Georgia Tech).