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

Cites work

scientific article; zbMATH DE number 1306899 (Why is no real title available?)
scientific article; zbMATH DE number 7204496 (Why is no real title available?)
A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
A new approach to dynamic all pairs shortest paths
Algorithm Theory - SWAT 2004
All-Pairs Almost Shortest Paths
An On-Line Edge-Deletion Problem
Approximate distance oracles
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
Decremental all-pairs shortest paths in deterministic near-linear time
Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound
Dynamic Low-Stretch Spanning Trees in Subpolynomial Time
Dynamic approximate all-pairs shortest paths in undirected graphs
Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
Dynamic low-stretch trees via dynamic low-diameter decompositions
Fully dynamic all-pairs shortest paths: breaking the \(O(n)\) barrier
Fully dynamic randomized algorithms for graph spanners
Graph partitioning using single commodity flows
Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
Improved dynamic algorithms for maintaining approximate shortest paths under deletions
Maintaining minimum spanning forests in dynamic graphs
Maintaining shortest paths under deletions in weighted directed graphs
Near-Linear Time Construction of Sparse Neighborhood Covers
On dynamic shortest paths problems
Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
Subcubic equivalences between path, matrix, and triangle problems
Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture

This page was built for publication: A new deterministic algorithm for fully dynamic all-pairs shortest paths

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