Data: 11/02/2021, às 16:00 horas (GMT-3, horário de Brasília).
Título: Conjuntos independentes, emparelhamentos e arborecências geradoras folhudas
Palestrante: Cristina Fernandes (USP)


Resumo: O Problema MaxLeaves consiste em, dado um grafo dirigido enraizado, encontrar uma arborecência geradora com o número máximo de folhas. Mostraremos uma surpreendente relação entre MaxLeaves em grafos dirigidos acíclicos e o problema de encontrar um conjunto independente de peso máximo (MIS) em grafos livres de garras de um certo tamanho. Desta relação, usando emparelhamentos máximos, derivamos uma 7/5-approximação para MaxLeaves em grafos dirigidos acíclicos.

Este trabalho é o resultado de uma colaboração com Carla N. Lintzmayer.