Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time
DOI10.1137/20M1312149zbMath1479.05296OpenAlexW2909578366MaRDI QIDQ5020731
Maximilian Probst Gutenberg, Christian Wulff-Nilsen, Aaron Bernstein
Publication date: 7 January 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m1312149
reachabilitydata structuresstrongly connected componentsdynamic graph algorithmsES-treesingle-source reachability
Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Randomized algorithms (68W20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fully-dynamic min-cut
- Finding paths and deleting edges in directed acyclic graphs
- A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time
- Improved Deterministic Algorithms for Decremental Reachability and Strongly Connected Components
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance
- Near-optimal fully-dynamic graph connectivity
- Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
- Improved Dynamic Reachability Algorithms for Directed Graphs
- An On-Line Edge-Deletion Problem
- Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time
- Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
- Decremental Dynamic Connectivity
- A New Approach to Incremental Cycle Detection and Related Problems
- Decremental single-source reachability in planar digraphs
- New algorithms and hardness for incremental single-source shortest paths in directed graphs
- An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs
- Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- An Experimental Study of Dynamic Algorithms for Transitive Closure
- A new approach to dynamic all pairs shortest paths
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Algorithms – ESA 2004
- Depth-First Search and Linear Graph Algorithms
- Dynamic graph connectivity in polylogarithmic worst case time
- Faster Deterministic Fully-Dynamic Graph Connectivity
This page was built for publication: Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time
