Yoshiko Wakabayashi
IME-USP
Sexta-feira, 20 de abril de 2007, 14:00
Anfiteatro do NUMEC
Resumo:
O tópico central deste seminário é o problema que consiste em encontrar, num dado grafo conexo, uma árvore geradora com o número máximo de folhas. Chamaremos este problema de MaxFolha. Sabe-se que este problema é NP-difícil, mesmo para grafos cúbicos.
Em termos de algoritmos de aproximação, o melhor resultado que se conhece para o MaxFolha é uma 2-aproximação obtida por Solis-Oba em 1998. Para grafos cúbicos, em 2002, Lorys e Zwozniak obtiveram uma 7/4-aproximação.
Mencionaremos alguns resultados recentes sobre limitantes inferiores e superiores para o número máximo de folhas de uma árvore geradora em grafos especiais. Apresentaremos também uma 5/3-aproximação para o MaxFolha em grafos cúbicos.
Alguns dos resultados mais recentes que apresentaremos fazem parte de um trabalho em andamento que tem a colaboração de José Correa (Chile), Cristina G. Fernandes (USP) e Martín Matamala (Chile).