A new deterministic algorithm for fully dynamic all-pairs shortest paths
From MaRDI portal
Publication:6499294
DOI10.1145/3564246.3585196WikidataQ130910232 ScholiaQ130910232MaRDI QIDQ6499294
Publication date: 8 May 2024
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On dynamic shortest paths problems
- Maintaining Minimum Spanning Forests in Dynamic Graphs
- Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs
- Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization
- Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier
- Fully dynamic randomized algorithms for graph spanners
- An On-Line Edge-Deletion Problem
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Subcubic Equivalences Between Path, Matrix, and Triangle Problems
- Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
- All-Pairs Almost Shortest Paths
- Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
- Dynamic Low-Stretch Spanning Trees in Subpolynomial Time
- Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
- Approximate distance oracles
- Dynamic low-stretch trees via dynamic low-diameter decompositions
- A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
- Algorithm Theory - SWAT 2004
- Deterministic decremental single source shortest paths: beyond the o(mn) bound
- A new approach to dynamic all pairs shortest paths
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
- Graph partitioning using single commodity flows
- Decremental all-pairs shortest paths in deterministic near-linear time
This page was built for publication: A new deterministic algorithm for fully dynamic all-pairs shortest paths