Title: Connectivity Problems on Temporal Graphs

Speaker: Ana Shirley Ferreira da Silva (Universidade Federal do Ceará UFC, Brasil & visiting DISIA)

Location: Aula 205 (ex 32) – DISIA – Viale Morgagni 59

Abstract:A temporal graph is a graph that changes in time, meaning that, at each timestamp, only a subset of the edges is active. These structure models all sorts of real-life situations, from social networks to public transportation, having also been used for contact tracing during the COVID pandemic. Despite its broad applicability, and despite being around for more than two decades, only recently has this structure received more attention from the community. In this talk, we will discuss how to bring some connectivity concepts to the temporal context, and we will learn about the state of the art of complexity results of the related problems. Additionally, we will see various possible adaptations of Menger’s Theorem, only a few of which also hold on temporal graphs.

Biosketch: Ana Silva is Associate Professor at the Mathematics Department of Universidade Federal do Ceará, Brazil, and is currently a Visiting Professor at the Universitá degli Studi di Firenze (Italy). She obtained her PhD degree in Mathematics and Computer Science by the Université de Grenoble (France) in November 2010 under the supervision of Frédéric Maffray. She was head of the Math Department at UFC from 2013 to 2015, and was a member of the Gender Committee of the Brazilian Mathematics Society from 2020 to 2021. In 2014, she received the L’Óreal/UNESCO/ABC Prize for Women in Science, and in 2021 was elected affiliated member of the ABC (Academia Brasileira de Ciências), a position that she will occupy until December 2025. Her work concerns mainly graph problems, in particular coloring problems and convexity problems, and lately she has been interested in Temporal Graphs.