A new deterministic algorithm for fully dynamic all-pairs shortest paths

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