License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6329/
Go to the corresponding LIPIcs Volume Portal

Georgiadis, Loukas ; Italiano, Giuseppe F. ; Parotsidis, Nikos

Incremental 2-Edge-Connectivity in Directed Graphs

pdf-format:
LIPIcs-ICALP-2016-49.pdf (1 MB)

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.
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI