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.
@InProceedings{georgiadis_et_al:LIPIcs.ICALP.2016.49, author = {Georgiadis, Loukas and Italiano, Giuseppe F. and Parotsidis, Nikos}, title = {{Incremental 2-Edge-Connectivity in Directed Graphs}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {49:1--49:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.49}, URN = {urn:nbn:de:0030-drops-63292}, doi = {10.4230/LIPIcs.ICALP.2016.49}, annote = {Keywords: 2-edge connectivity on directed graphs; dynamic graph algorithms; incremental algorithms.} }
Feedback for Dagstuhl Publishing