Fully dynamic single-source reachability in practice: An experimental study
Hanauer K, Henzinger MH, Schulz C. 2020. Fully dynamic single-source reachability in practice: An experimental study. 2020 Symposium on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 106–119.
Download (ext.)
https://arxiv.org/abs/1905.01216
[Preprint]
Conference Paper
| Published
| English
Scopus indexed
Author
Hanauer, Kathrin;
Henzinger, MonikaISTA ;
Schulz, Christian
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.
Publishing Year
Date Published
2020-01-01
Proceedings Title
2020 Symposium on Algorithm Engineering and Experiments
Publisher
Society for Industrial and Applied Mathematics
Page
106-119
Conference
ALENEX: Symposium on Algorithm Engineering and Experiments
Conference Location
Salt Lake City, UT, United States
Conference Date
2020-01-05 – 2020-01-06
IST-REx-ID
Cite this
Hanauer K, Henzinger MH, Schulz C. Fully dynamic single-source reachability in practice: An experimental study. In: 2020 Symposium on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2020:106-119. doi:10.1137/1.9781611976007.9
Hanauer, K., Henzinger, M. H., & Schulz, C. (2020). Fully dynamic single-source reachability in practice: An experimental study. In 2020 Symposium on Algorithm Engineering and Experiments (pp. 106–119). Salt Lake City, UT, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611976007.9
Hanauer, Kathrin, Monika H Henzinger, and Christian Schulz. “Fully Dynamic Single-Source Reachability in Practice: An Experimental Study.” In 2020 Symposium on Algorithm Engineering and Experiments, 106–19. Society for Industrial and Applied Mathematics, 2020. https://doi.org/10.1137/1.9781611976007.9.
K. Hanauer, M. H. Henzinger, and C. Schulz, “Fully dynamic single-source reachability in practice: An experimental study,” in 2020 Symposium on Algorithm Engineering and Experiments, Salt Lake City, UT, United States, 2020, pp. 106–119.
Hanauer K, Henzinger MH, Schulz C. 2020. Fully dynamic single-source reachability in practice: An experimental study. 2020 Symposium on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 106–119.
Hanauer, Kathrin, et al. “Fully Dynamic Single-Source Reachability in Practice: An Experimental Study.” 2020 Symposium on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2020, pp. 106–19, doi:10.1137/1.9781611976007.9.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1905.01216