Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
From MaRDI portal
Publication:2910856
DOI10.1137/090776573zbMath1247.68340OpenAlexW2015725509MaRDI QIDQ2910856
Publication date: 12 September 2012
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/090776573
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items
Approximate distance oracles with improved stretch for sparse graphs, Dynamic Single-Source Shortest Paths in Erdös-Rényi Random Graphs, Incremental algorithm for maintaining a DFS tree for undirected graphs, On Dynamic DFS Tree in Directed Graphs, On dynamic shortest paths problems, Average update times for fully-dynamic all-pairs shortest paths, Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version), Unnamed Item, Dynamic graph coloring, Randomization for Efficient Dynamic Graph Algorithms, Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs, Constructing Light Spanners Deterministically in Near-Linear Time, Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs, Unnamed Item, Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization, Dynamic Maintenance of a Shortest-Path Tree on Homogeneous Batches of Updates, Approximate distance oracles with improved stretch for sparse graphs, Constructing light spanners deterministically in near-linear time, Fully Dynamic Maximal Matching in $O(\log n)$ Update Time, Dynamically Maintaining Shortest Path Trees under Batches of Updates
