Seminario online - 2-Connectivity in Directed Graphs
Mercoledì 13 Gennaio alle ore 15:30, il prof. Giuseppe F. Italiano, Luiss University (http://docenti.luiss.it/italiano/), terrà un seminario online tramite la piattaforma Teams, per la durata orientativa di 1h.
Title: "2-Connectivity in Directed Graphs"
Summary: We survey some recent results on 2-edge and 2-vertex connectivity in directed graphs. Despite being complete analogs of the corresponding notions on undirected graphs, in digraphs 2-connectivity has a much richer and more complicated structure. For undirected graphs it has been known for over 40 years how to compute all bridges, articulation points, 2-edge- and 2-vertex-connected components in linear time, by simply using depth first search. In the case of digraphs, however, the very same problems have been much more challenging and have been tackled only very recently.