Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.49
URN: urn:nbn:de:0030-drops-63292
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6329/
Georgiadis, Loukas ; Italiano, Giuseppe F. ; Parotsidis, Nikos
Incremental 2-Edge-Connectivity in Directed Graphs
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{georgiadis_et_al:LIPIcs:2016:6329,
author = {Loukas Georgiadis and Giuseppe F. Italiano and Nikos Parotsidis},
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 = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6329},
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.}
}
| Keywords: | 2-edge connectivity on directed graphs; dynamic graph algorithms; incremental algorithms. | |
| Seminar: | 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 23.08.2016 |
