On dynamic shortest paths problems

DOI10.1007/s00453-010-9401-5zbMath1244.68091OpenAlexW2038084411WikidataQ60299140 ScholiaQ60299140MaRDI QIDQ639278

Uri Zwick, Liam Roditty

Publication date: 20 September 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9401-5

zbMATH Keywords

randomized algorithmshortest pathsdynamic algorithmsspannersweighted directed graphtime-complexity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

Fully-Dynamic Approximation of Betweenness Centrality ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Distributed construction of purely additive spanners ⋮ Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Constructing Light Spanners Deterministically in Near-Linear Time ⋮ Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Constructing light spanners deterministically in near-linear time ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Approximating Betweenness Centrality in Fully Dynamic Networks ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• On sparse spanners of weighted graphs
• All pairs shortest distances for graphs with small integer length edges
• A new approach to all-pairs shortest paths on real-weighted graphs
• Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
• Experimental analysis of dynamic all pairs shortest path algorithms
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• Undirected single-source shortest paths with positive integer weights in linear time
• High-Probability Parallel Transitive-Closure Algorithms
• Dynamic Subgraph Connectivity with Geometric Applications
• Improved Dynamic Reachability Algorithms for Directed Graphs
• Approximate distance oracles
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• Graph spanners
• An On-Line Edge-Deletion Problem
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• An Incremental Algorithm for a Generalization of the Shortest-Path Problem
• Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• Algorithm Theory - SWAT 2004
• A Shortest Path Algorithm for Real-Weighted Undirected Graphs
• Algorithms – ESA 2004
• Automata, Languages and Programming
• Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths