Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs

DOI10.1007/978-3-662-47672-7_59MaRDI QIDQ3448830zbMATH OpenOpenAlexFDO

Authors Sebastian Krinninger, Danupon Nanongkai, Monika R. Henzinger

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.03856

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

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 $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=Theta(n^{1.5})$ the running time is $O(n^{2.47})$, just barely below $mn=Theta(n^{2.5})$. In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of $ildeO(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=Theta(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.

Recommendations

• Improved Dynamic Reachability Algorithms for Directed Graphs
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
• Decremental single-source reachability in planar digraphs
• Improved deterministic algorithms for decremental reachability and strongly connected components
• Decremental strongly connected components and single-source reachability in near-linear time
• Decremental strongly-connected components and single-source reachability in near-linear time
• scientific article; zbMATH DE number 4086991
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• Reachability Problems on Directed Graphs

Cites work

• An On-Line Edge-Deletion Problem
• Decremental maintenance of strongly connected components
• Finding paths and deleting edges in directed acyclic graphs
• High-Probability Parallel Transitive-Closure Algorithms
• scientific article; zbMATH DE number 1306899 (Why is no real title available?)
• Improved deterministic algorithms for decremental reachability and strongly connected components
• Improved Dynamic Reachability Algorithms for Directed Graphs
• Subcubic equivalences between path, matrix, and triangle problems
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
• Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture

Cited in

(15)

• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• Improved deterministic algorithms for decremental reachability and strongly connected components
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• scientific article; zbMATH DE number 1104331 (Why is no real title available?)
• Decremental single-source reachability in planar digraphs
• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• Decremental strongly connected components and single-source reachability in near-linear time
• Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
• Decremental data structures for connectivity and dominators in directed graphs
• Fully Dynamic Single-Source Reachability in Practice: An Experimental Study
• Decremental strongly-connected components and single-source reachability in near-linear time
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
• Decremental maintenance of strongly connected components
• Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
• An efficient strongly connected components algorithm in the fault tolerant model

This page was built for publication: Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448830)