Paulo Feofiloff
IME-USP
Sexta-feira, 21 de maio de 2004, 14:00
Sala 267, Bloco A, IME-USP
Resumo:
A primeira parte desta palestra será um breve introdução ao conceito de fixed-parameter tractability e ao problema da cobertura. (Uma cobertura ou vertex cover de um grafo é um conjunto de vértices que contém pelo menos uma das pontas de cada aresta do grafo.)
A segunda parte tratará de um algoritmo exponencial para o
seguinte problema:
Dado um grafo bipartido (G,V_1,V_2), encontrar uma
cobertura mínima X tal que |X \cap V_1| <= k_1 e
|X \cap V_2| <= k_2.
Bibliografia:
J. Chen e I.A. Kanj, "Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms", J. of Computer and Systems Sciences, 2003.
R.G. Downey e M.R. Fellows, Parameterized Complexity, Springer-Verlag, 1999.
L. Lovász e M.D. Plummer, Matching Theory, North-Holland, 1986.