Yoshiko Wakabayashi
IME-USP
Sexta-feira, 17 de agosto de 2007, 14:00
Anfiteatro do NUMEC
Resumo:
Dado um grafo G e uma família F de grafos, o problema do F-empacotamento consiste em encontrar em G um conjunto de subgrafos disjuntos nos vértices, cada qual isomorfo a um elemento de F, e que tenha o maior número possível de arestas. Quando F = {K_2} temos o bem-conhecido problema do emparelhamento máximo. Quando F={K_3} o problema já é APX-difícil. Apresentaremos algoritmos de aproximação e resultados de inaproximabilidade para o caso em que F é uma família de cliques, F={K_2, K_3,...K_r}. Este trabalho tem a co-autoria de F. Chataigner, G. Manic e R. Yuster.