Improved algorithms for decremental single-source reachability on directed graphs
Henzinger MH, Krinninger S, Nanongkai D. 2015. Improved algorithms for decremental single-source reachability on directed graphs. 42nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 725β736.
Download (ext.)
https://arxiv.org/abs/1612.03856
[Preprint]
Conference Paper
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA ;
Krinninger, Sebastian;
Nanongkai, Danupon
Series Title
LNCS
Abstract
Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with π(ππ) total update time, where π is the number of edges and π is the number of nodes in the graph [Henzinger et al. STOC 2014]. The algorithm is a combination of several different algorithms, each for a different π vs. π trade-off. For the case of π=Ξ(π1.5) the running time is π(π2.47), just barely below ππ=Ξ(π2.5). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of πΜ (min(π7/6π2/3,π3/4π5/4+π(1),π2/3π4/3+π(1)+π3/7π12/7+π(1))). This gives, e.g., π(π2.36) for the notorious case π=Ξ(π1.5). We obtain the same upper bounds for the problem of maintaining the strongly connected components of a directed graph undergoing edge deletions. Our algorithms are correct with high probabililty against an oblivious adversary.
Publishing Year
Date Published
2015-01-01
Proceedings Title
42nd International Colloquium on Automata, Languages and Programming
Publisher
Springer Nature
Volume
9134
Page
725 - 736
Conference
ICALP: International Colloquium on Automata, Languages, and Programming
Conference Location
Kyoto, Japan
Conference Date
2015-07-06 – 2015-07-10
ISBN
ISSN
IST-REx-ID
Cite this
Henzinger MH, Krinninger S, Nanongkai D. Improved algorithms for decremental single-source reachability on directed graphs. In: 42nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:725-736. doi:10.1007/978-3-662-47672-7_59
Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2015). Improved algorithms for decremental single-source reachability on directed graphs. In 42nd International Colloquium on Automata, Languages and Programming (Vol. 9134, pp. 725β736). Kyoto, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-47672-7_59
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. βImproved Algorithms for Decremental Single-Source Reachability on Directed Graphs.β In 42nd International Colloquium on Automata, Languages and Programming, 9134:725β36. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_59.
M. H. Henzinger, S. Krinninger, and D. Nanongkai, βImproved algorithms for decremental single-source reachability on directed graphs,β in 42nd International Colloquium on Automata, Languages and Programming, Kyoto, Japan, 2015, vol. 9134, pp. 725β736.
Henzinger MH, Krinninger S, Nanongkai D. 2015. Improved algorithms for decremental single-source reachability on directed graphs. 42nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 725β736.
Henzinger, Monika H., et al. βImproved Algorithms for Decremental Single-Source Reachability on Directed Graphs.β 42nd International Colloquium on Automata, Languages and Programming, vol. 9134, Springer Nature, 2015, pp. 725β36, doi:10.1007/978-3-662-47672-7_59.
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 1612.03856