Seminário de Teoria da Computação e Combinatória
Título: Um Algoritmo Eficiente para Imersão de Árvores em Grafos Expansores
Palestrante: Domingos Dellamonica Jr
Local: Sala 267 do Bloco A
Data: sexta, 18 de novembro, às 14:00
Resumo:
Em 1987, Friedman e Pippenger provaram o seguinte resultado:
sejam n e d inteiros positivos; se G é um grafo
(n,d)-expansor, isto é, um grafo para o qual todo conjunto
com r <= 2n - 2 vértices tem pelo menos (d + 1)*r vizinhos,
e T é uma árvore com grau máximo limitado por d e |V(T)| <=
n, então G possui T como subgrafo. A prova deste teorema
não fornecia diretamente um algoritmo (polinomial) para
encontrar a árvore T em G (o resultado era existencial).
Conseguimos acrescentar um ingrediente à demonstração
original de forma que esta passa a ter uma versão
algorítmica eficiente (polinomial) que efetivamente encontra
T dentro de G.
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/
Fórum