2026-08-14T20:19:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6329 2024-03-06T10:37:44Z ddc:004 open_access

Incremental 2-Edge-Connectivity in Directed Graphs Georgiadis, Loukas Italiano, Giuseppe F. Parotsidis, Nikos 2-edge connectivity on directed graphs; dynamic graph algorithms; incremental algorithms. We present an algorithm that can update the 2-edge-connected blocks of a directed graph with n vertices through a sequence of m edge insertions in a total of O(m*n) time. After each insertion, we can answer the following queries in asymptotically optimal time: - Test in constant time if two query vertices v and w are 2-edge-connected. Moreover, if v and w are not 2-edge-connected, we can produce in constant time a “witness” of this property, by exhibiting an edge that is contained in all paths from v to w or in all paths from w to v. - Report in O(n) time all the 2-edge-connected blocks of G. This is the first dynamic algorithm for 2-connectivity problems on directed graphs, and it matches the best known bounds for simpler problems, such as incremental transitive closure. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Loukas Georgiadis and Giuseppe F. Italiano and Nikos Parotsidis 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.49 urn:nbn:de:0030-drops-63292 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.49 eng https://creativecommons.org/licenses/by/3.0/legalcode