Edge-disjoint Branchings in Temporal Digraphs (Palestra remota)
Expositor: Ana Silva
Instituição:UFC
Data e Horário: 17/12/2020 | 17:00 hs

Resumo: A temporal digraph is a digraph that has a dynamic nature, meaning that it exists through (a discretelabeled) time and at each timestamp only a subdigraph 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).