On dynamic shortest paths problems
From MaRDI portal
Publication:639278
DOI10.1007/s00453-010-9401-5zbMath1244.68091OpenAlexW2038084411WikidataQ60299140 ScholiaQ60299140MaRDI QIDQ639278
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
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
