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.SEA.2020.14
URN: urn:nbn:de:0030-drops-120887
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12088/
Go to the corresponding LIPIcs Volume Portal

Hanauer, Kathrin ; Henzinger, Monika ; Schulz, Christian

Faster Fully Dynamic Transitive Closure in Practice

pdf-format:
LIPIcs-SEA-2020-14.pdf (1 MB)

Abstract

The fully dynamic transitive closure problem asks to maintain reachability information in a directed graph between arbitrary pairs of vertices, while the graph undergoes a sequence of edge insertions and deletions. The problem has been thoroughly investigated in theory and many specialized algorithms for solving it have been proposed in the last decades. In two large studies [Frigioni ea, 2001; Krommidas and Zaroliagis, 2008], a number of these algorithms have been evaluated experimentally against simple, static algorithms for graph traversal, showing the competitiveness and even superiority of the simple algorithms in practice, except for very dense random graphs or very high ratios of queries. A major drawback of those studies is that only small and mostly randomly generated graphs are considered.
In this paper, we engineer new algorithms to maintain all-pairs reachability information which are simple and space-efficient. Moreover, we perform an extensive experimental evaluation on both generated and real-world instances that are several orders of magnitude larger than those in the previous studies. Our results indicate that our new algorithms outperform all state-of-the-art algorithms on all types of input considerably in practice.

BibTeX - Entry

@InProceedings{hanauer_et_al:LIPIcs:2020:12088,
  author =	{Kathrin Hanauer and Monika Henzinger and Christian Schulz},
  title =	{{Faster Fully Dynamic Transitive Closure in Practice}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Simone Faro and Domenico Cantone},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12088},
  URN =		{urn:nbn:de:0030-drops-120887},
  doi =		{10.4230/LIPIcs.SEA.2020.14},
  annote =	{Keywords: Dynamic Graph Algorithms, Reachability, Transitive Closure}
}

Keywords: Dynamic Graph Algorithms, Reachability, Transitive Closure
Collection: 18th International Symposium on Experimental Algorithms (SEA 2020)
Issue Date: 2020
Date of publication: 12.06.2020
Supplementary Material: Source code and instances are available at https://dyreach.taa.univie.ac.at/transitive-closure.

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