Paulo Feofiloff
IME-USP
Sexta-feira, 16 de março de 2007, 14:00
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).