apresentam tipicamente tópicos relacionados a AA.
Todos são bem-vindos!
Os Seminários de TCC esse ano ocorrerão no Anfiteatro do NUMEC
(prédio ao lado do bloco C), sextas às 14h.
O primeiro seminário do semestre será na semana que vem,
dia 16 de março. Abaixo segue a informação completa.
Seminário de Teoria da Computação e Combinatória
Título: kMST é FPT: color-coding e hashing perfeito
Palestrante: Paulo Feofiloff
Data: sexta, 16 de março, às 14:00
Local: Anfiteatro do NUMEC-USP
Resumo:
Dado um número inteiro positivo k e um grafo G com pesos
não-negativos nas arestas, encontrar uma subárvore de G
de peso mínimo dentre as que têm k vértices. Esse é o
problema kMST.
É claro que o problema pode ser resolvido em tempo O(n^k),
sendo n o número de vértices de G. Betzler, baseada no
trabalho de Alon, Yuster e Zwick, mostrou que existe um
algoritmo para o kMST que consome tempo 2^{O(k)} n^2 lg n.
A existência de um tal algoritmo prova que o problema
pertence à classe de complexidade FPT definida por Downey
e Fellows. O algoritmo envolve a combinação de três
idéias muito diferentes: color-coding, geração de árvores
e hashing perfeito. Esta palestra descreverá um algoritmo
um pouco mais simples, que envolve apenas color-coding e
hashing perfeito. O algoritmo consome tempo O(2^{13k} n^3).
------------------------------------------------------------
Todos são bem-vindos!!
Para mais informações sobre o seminário de TCC, visite a página:
http://www.ime.usp.br/~cris/seminarios/