Deterministic incremental APSP with polylogarithmic update time and stretch

Cites Work

Unnamed Item
On dynamic shortest paths problems
On the power of randomization in on-line algorithms
Fully dynamic all pairs shortest paths with real edge weights
Deterministic Dictionaries
Maintaining Shortest Paths Under Deletions in Weighted Directed 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
Towards polynomial lower bounds for dynamic problems
Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Maintaining information in fully dynamic trees with top trees
Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier
Fully dynamic randomized algorithms for graph spanners
Approximate distance oracles
Worst-case update times for fully-dynamic all-pairs shortest paths
An On-Line Edge-Deletion Problem
Fully dynamic all-pairs shortest paths with worst-case update-time revisited
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
Parallel approximate undirected shortest paths via low hop emulators
Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
Distance Labels with Optimal Local Stretch
Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
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 Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths
A new approach to dynamic all pairs shortest paths
Computing and Combinatorics
Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
Decremental all-pairs shortest paths in deterministic near-linear time

This page was built for publication: Deterministic incremental APSP with polylogarithmic update time and stretch