Data: 04/06/2020, às 14:00 horas (GMT-3, horário de Brasília).
Título: Arborescências geradoras folhudas em DAGs
Palestrante: Carla Negri Lintzmayer (UFABC)


Resumo: Considere o problema de, dado um digrafo D, encontrar uma arborescência geradora de D, se uma existir, com o maior número de folhas. Consideramos o caso em que D é um digrafo acíclico enraizado, que é MaxSNP-difícil e para o qual existe uma 2-aproximação.
Nós melhoramos esse resultado, apresentando uma 3/2-aproximação.

Trabalho em conjunto com Cristina Fernandes.