Deterministic incremental APSP with polylogarithmic update time and stretch
From MaRDI portal
Cites work
- 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
- A subquadratic-time algorithm for decremental single-source shortest paths
- Algorithm Theory - SWAT 2004
- An On-Line Edge-Deletion Problem
- Approximate distance oracles
- Computing and Combinatorics
- Decremental all-pairs shortest paths in deterministic near-linear time
- Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
- Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound
- Deterministic dictionaries
- Distance Labels with Optimal Local Stretch
- Dynamic approximate all-pairs shortest paths in undirected graphs
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
- Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
- Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
- Fully dynamic all pairs shortest paths with real edge weights
- Fully dynamic all-pairs shortest paths with worst-case update-time revisited
- Fully dynamic all-pairs shortest paths: breaking the O(n) barrier
- Fully dynamic randomized algorithms for graph spanners
- Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
- Improved dynamic algorithms for maintaining approximate shortest paths under deletions
- Maintaining information in fully dynamic trees with top trees
- Maintaining shortest paths under deletions in weighted directed graphs
- On dynamic shortest paths problems
- On the power of randomization in on-line algorithms
- Parallel approximate undirected shortest paths via low hop emulators
- Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
- Towards polynomial lower bounds for dynamic problems
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Worst-case update times for fully-dynamic all-pairs shortest paths
Cited in
(2)
This page was built for publication: Deterministic incremental APSP with polylogarithmic update time and stretch
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499295)
