Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
2015 (English)In: Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, Springer Berlin/Heidelberg, 2015, 725-736 p.Conference paper (Refereed)
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 o(mn) total update time, where m is the number of edges and n 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 m vs. n trade-off. For the case of m=Θ(n 1.5 ) the running time is O(n 2.47 ) , just barely below mn=Θ(n 2.5 ) . In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of O ~ (min(m 7/6 n 2/3 ,m 3/4 n 5/4+o(1) ,m 2/3 n 4/3+o(1) +m 3/7 n 12/7+o(1) )) . This gives, e.g., O(n 2.36 ) for the notorious case m=Θ(n 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.
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2015. 725-736 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 9134
Dynamic graph algorithms, reachability
IdentifiersURN: urn:nbn:se:kth:diva-165849DOI: 10.1007/978-3-662-47672-7_59ScopusID: 2-s2.0-84950161208ISBN: 978-3-662-47672-7OAI: oai:DiVA.org:kth-165849DiVA: diva2:808917
The 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), 6-10 July 2015, Kyoto, Japan
QC 201507152015-04-292015-04-292015-07-15Bibliographically approved