Fully Dynamic Single-Source Reachability in Practice: An Experimental Study

Kathrin Hanauer, Monika Henzinger, Christian Schulz

Veröffentlichungen: Beitrag in BuchBeitrag in KonferenzbandPeer Reviewed

Abstract

Given a directed graph and a source vertex, the fully dynamic single-source reachability problem is to maintain the set of vertices that are reachable from the given vertex, subject to edge deletions and insertions. It is one of the most fundamental problems on graphs and appears directly or indirectly in many and varied applications. While there has been theoretical work on this problem, showing both linear conditional lower bounds for the fully dynamic problem and insertions-only and deletions-only upper bounds beating these conditional lower bounds, there has been no experimental study that compares the performance of fully dynamic reachability algorithms in practice. Previous experimental studies in this area concentrated only on the more general all-pairs reachability or transitive closure problem and did not use real-world dynamic graphs. In this paper, we bridge this gap by empirically studying an extensive set of algorithms for the single-source reachability problem in the fully dynamic setting. In particular, we design several fully dynamic variants of well-known approaches to obtain and maintain reachability information with respect to a distinguished source. Moreover, we extend the existing insertions-only or deletions-only upper bounds into fully dynamic algorithms. Even though the worst-case time per operation of all the fully dynamic algorithms we evaluate is at least linear in the number of edges in the graph (as is to be expected given the conditional lower bounds) we show in our extensive experimental evaluation that their performance differs greatly, both on generated as well as on real-world instances.

OriginalspracheEnglisch
Titel2020 Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2020
Redakteure*innenGuy Blelloch, Irene Finocchi
Seiten106-119
Seitenumfang14
ISBN (elektronisch)9781611976007
DOIs
PublikationsstatusVeröffentlicht - 5 Jan. 2020
VeranstaltungALENEX 2020 - Salt Lake City, Utah, USA / Vereinigte Staaten
Dauer: 5 Jan. 20207 Jan. 2020
https://www.siam.org/conferences/cm/conference/soda20

Konferenz

KonferenzALENEX 2020
Land/GebietUSA / Vereinigte Staaten
OrtSalt Lake City, Utah
Zeitraum5/01/207/01/20
Internetadresse

ÖFOS 2012

  • 102031 Theoretische Informatik

Zitationsweisen