Data: 03/09/2020, às 14:00 horas (GMT-3, horário de Brasília).
Título: Edge-disjoint Branchings in Temporal Digraphs
Palestrante: Ana Silva (UFC)
Abstract: A temporal digraph is a digraph that has a dynamic nature, meaning that it exists through (a discrete-labeled) time and at each timestamp only a subgraph of the base digraph is active. Despite being around for more than two decades, only recently this structure has received more attention from the community. In this talk, I will formally present the structure and discuss the difficulties related to modeling classic digraph concepts on it. Then, I will talk about the possible interpretations of what edge-disjoint branchings should be in these structures, and present a recent result on edge-disjoint branchings that says that most of these interpretations translate into NP-complete problems. This is in stark contrast with the static version of the problem which is known to be polynomial thanks to the famous Edmonds' Theorem on edge-disjoint branchings.
This is a joint work with Victor Campos (UFC, Brazil), Raul Lopes (UFC, Brazil) and Andréa Marino (Uni. degli Studi di Firenze, Italy).