Palestra: Arborescências geradoras folhudas em DAGs
Resumo: Assumindo que P ≠ NP, uma grande variedade de problemas de otimização não podem ser resolvidos exatamente em tempo polinomial. Algoritmos de aproximação são uma maneira de lidar com esses problemas NP-difíceis. Eles são algoritmos eficientes que têm garantias teóricas para a razão entre o custo da solução encontrada pelo algoritmo e o custo de uma solução ótima para o problema. Nessa palestra, mostrarei alguns resultados sobre algoritmos de aproximação para o problema das Arborescências geradoras folhudas em DAGs. Esse problema consiste em, dado um digrafo acíclico enraizado, encontrar uma arborescência geradora com o maior número de folhas. Os resultados que mostrarei fazem parte de trabalhos em conjunto com a profa. Cristina Gomes Fernandes, da USP.
Short-bio: Possui graduação em Ciência da Computação pela Universidade Estadual de Maringá (2011), doutorado em Ciência da Computação pela Universidade Estadual de Campinas (2016) com período sanduíche na Université de Nantes, França (2015), e pós-doutorado na Universidade Estadual de Campinas (2017). Atualmente é professora adjunta na Universidade Federal do ABC. Seus interesses de pesquisa se concentram na área de Teoria da Computação, com ênfase em Projeto e Análise de Algoritmos, Otimização Combinatória e Teoria dos Grafos. É atual vice-coordenadora do programa de pós-graduação em computação da UFABC e vice-coordenadora da Comissão Especial em Algoritmos, Combinatória e Otimização (CEACO) da Sociedade Brasileira de Computação. Recebeu o Prêmio L’Oréal para Mulheres na Ciência em 2023, na área de Matemática.