Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs
From MaRDI portal
Publication:2805514
DOI10.1137/130938670zbMath1335.05078OpenAlexW2342666984MaRDI QIDQ2805514
Publication date: 12 May 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/130938670
Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)
Related Items (6)
Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time ⋮ Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Parametric Shortest-Path Algorithms via Tropical Geometry
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On dynamic shortest paths problems
- Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization
- Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
- Improved Dynamic Reachability Algorithms for Directed Graphs
- An On-Line Edge-Deletion Problem
- An Incremental Algorithm for a Generalization of the Shortest-Path Problem
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- A new approach to dynamic all pairs shortest paths
- Compact oracles for reachability and approximate distances in planar digraphs
- Maintaining shortest paths under deletions in weighted directed graphs
- Computing and Combinatorics
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
This page was built for publication: Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs
