Maintaining shortest paths under deletions in weighted directed graphs
From MaRDI portal
Publication:2805514
DOI10.1137/130938670zbMATH Open1335.05078OpenAlexW2342666984MaRDI QIDQ2805514FDOQ2805514
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
Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Signed and weighted graphs (05C22) Paths and cycles (05C38)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- An Incremental Algorithm for a Generalization of the Shortest-Path Problem
- A new approach to dynamic all pairs shortest paths
- An On-Line Edge-Deletion Problem
- Compact oracles for reachability and approximate distances in planar digraphs
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- Maintaining shortest paths under deletions in weighted directed graphs
- Dynamic approximate all-pairs shortest paths in undirected graphs
- Improved Dynamic Reachability Algorithms for Directed Graphs
- On dynamic shortest paths problems
- Computing and Combinatorics
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
Cited In (10)
- Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time
- Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs
- Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
- Parametric Shortest-Path Algorithms via Tropical Geometry
- Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
- Maintaining shortest paths under deletions in weighted directed graphs
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- A new deterministic algorithm for fully dynamic all-pairs shortest paths
- Deterministic incremental APSP with polylogarithmic update time and stretch
- A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
This page was built for publication: Maintaining shortest paths under deletions in weighted directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2805514)
