Seminário de Teoria da Computação e Combinatória
Título: Subgrafos geradores k-conexos de peso médio mínimo e mais...
Palestrante: Cristina Gomes Fernandes
Local: Sala 267 do Bloco A
Data: sexta, 30 de setembro, às 14:00
Resumo:
Recentemente, Gubbala and Raghavachari (Latin'04) consideraram o
problema de encontrar um subgrafo gerador k-conexo de peso médio mínimo, num dado grafo k-conexo com pesos não-negativos nas arestas. Eles mostraram uma 3-aproximação para o caso de aresta-conexidade, e uma H_k-aproximação para o caso de vértice-conexidade, onde c \geq 6. Mostraremos um esquema que permite obter, para o problema de peso médio mínimo, as mesmas razões de aproximação conhecidas para o problema de encontrar um subgrafo gerador k-conexo de peso mínimo. Como conseqüência, deduzimos, para os problemas de peso médio mínimo, uma 2-aproximação para o caso de aresta-conexidade e uma 2H_k-aproximação para o caso de vértice-conexidade. O esquema pode ser aplicado para uma gama maior de problemas, estendendo um trabalho clássico de Megiddo, sobre otimização de funções racionais.
Este é um trabalho conjunto com José Correa (Chile) e Yoshiko
Wakabayashi.
Todos são bem-vindos!!
Para mais informações sobre o seminário de TCC, visite a página:
http://pronex-focos.incubadora.fapesp.br/portal/seminarios/