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

Cites Work

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

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)