2026-07-20T07:45:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6345 2024-03-06T10:38:02Z ddc:004 open_access

2-Connectivity in Directed Graphs (Invited Talk) Georgiadis, Loukas Italiano, Giuseppe F. Parotsidis, Nikos 2-edge and 2-vertex connectivity on directed graphs graph algorithms dominator trees We survey some recent results on 2-edge and 2-vertex connectivity problems in directed graphs. Despite being complete analogs of the corresponding notions on undirected graphs, in digraphs 2-vertex and 2-edge connectivity have a much richer and more complicated structure. It is thus not surprising that 2-connectivity problems on directed graphs appear to be more difficult than on undirected graphs. 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 required the development of new tools and techniques. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Loukas Georgiadis and Giuseppe F. Italiano and Nikos Parotsidis 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.1 urn:nbn:de:0030-drops-63451 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.1 eng https://creativecommons.org/licenses/by/3.0/legalcode