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.2017.42
URN: urn:nbn:de:0030-drops-74455
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7445/
Go to the corresponding LIPIcs Volume Portal

Georgiadis, Loukas ; Dueholm Hansen, Thomas ; Italiano, Giuseppe F. ; Krinninger, Sebastian ; Parotsidis, Nikos

Decremental Data Structures for Connectivity and Dominators in Directed Graphs

pdf-format:
LIPIcs-ICALP-2017-42.pdf (0.6 MB)

Abstract

We introduce a new dynamic data structure for maintaining the strongly connected components (SCCs) of a directed graph (digraph) under edge deletions, so as to answer a rich repertoire of connectivity queries. Our main technical contribution is a decremental data structure that supports sensitivity queries of the form "are u and v strongly connected in the graph G \ w?", for any triple of vertices u, v, w, while G undergoes deletions of edges. Our data structure processes a sequence of edge deletions in a digraph with $n$ vertices in O(m n log n) total time and O(n^2 log n) space, where m is the number of edges before any deletion, and answers the above queries in constant time. We can leverage our data structure to obtain decremental data structures for many more types of queries within the same time and space complexity. For instance for edge-related queries, such as testing whether two query vertices u and v are strongly connected in G \ e, for some query edge e.

As another important application of our decremental data structure, we provide the first nontrivial algorithm for maintaining the dominator tree of a flow graph under edge deletions. We present an algorithm that processes a sequence of edge deletions in a flow graph in O(m n log n) total time and O(n^2 log n) space. For reducible flow graphs we provide an O(mn)-time and O(m + n)-space algorithm. We give a conditional lower bound that provides evidence that these running times may be tight up to subpolynomial factors.

BibTeX - Entry

@InProceedings{georgiadis_et_al:LIPIcs:2017:7445,
  author =	{Loukas Georgiadis and Thomas Dueholm Hansen and Giuseppe F. Italiano and Sebastian Krinninger and Nikos Parotsidis},
  title =	{{Decremental Data Structures for Connectivity and Dominators in Directed Graphs}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{42:1--42:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7445},
  URN =		{urn:nbn:de:0030-drops-74455},
  doi =		{10.4230/LIPIcs.ICALP.2017.42},
  annote =	{Keywords: dynamic graph algorithms, decremental algorithms, dominator tree, strong connectivity under failures}
}

Keywords: dynamic graph algorithms, decremental algorithms, dominator tree, strong connectivity under failures
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

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