Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization
From MaRDI portal
Publication:2816298
DOI10.1137/140957299zbMath1339.05387arXiv1308.0776OpenAlexW2952708184MaRDI QIDQ2816298
Danupon Nanongkai, Sebastian Krinninger, Monika R. Henzinger
Publication date: 4 July 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1308.0776
Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items (10)
Approximate distance oracles with improved stretch for sparse graphs ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs ⋮ Constructing Light Spanners Deterministically in Near-Linear Time ⋮ Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Constructing light spanners deterministically in near-linear time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Faster algorithms for mean-payoff games
- On dynamic shortest paths problems
- On-line computation of minimal and maximal length paths
- On the power of randomization in on-line algorithms
- Fully dynamic all pairs shortest paths with real edge weights
- Planar graphs, negative weight edges, shortest paths, and near linear time
- All-Pairs Small-Stretch Paths
- Maintaining Minimum Spanning Forests in Dynamic Graphs
- Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization
- Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
- Approximating the Girth
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
- Fully dynamic randomized algorithms for graph spanners
- High-Probability Parallel Transitive-Closure Algorithms
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Approximate distance oracles
- Spanners and emulators with sublinear distance errors
- An On-Line Edge-Deletion Problem
- Incremental algorithms for minimal length paths
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Dynamic Perfect Hashing: Upper and Lower Bounds
- Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- Cuckoo hashing
- All-Pairs Almost Shortest Paths
- Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- Small Stretch Spanners on Dynamic Graphs
- Algorithm Theory - SWAT 2004
- Graph expansion and communication costs of fast matrix multiplication
- A new approach to dynamic all pairs shortest paths
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Maintaining shortest paths under deletions in weighted directed graphs
- Computing almost shortest paths
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
- Faster shortest-path algorithms for planar graphs
This page was built for publication: Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization
