Maintaining shortest paths under deletions in weighted directed graphs
From MaRDI portal
Publication:2805514
DOI10.1137/130938670zbMATH Open1335.05078OpenAlexW2342666984MaRDI QIDQ2805514FDOQ2805514
Authors: Aaron Bernstein 
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
Recommendations
- Maintaining shortest paths under deletions in weighted directed graphs
- Fully dynamic all pairs shortest paths with real edge weights
- scientific article; zbMATH DE number 2079363
- Dynamic approximate all-pairs shortest paths in undirected graphs
- Improved dynamic algorithms for maintaining approximate shortest paths under deletions
Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Signed and weighted graphs (05C22) Paths and cycles (05C38)
Cites Work
- 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
- Highway dimension, shortest paths, and provably efficient algorithms
- Compact oracles for reachability and approximate distances in planar digraphs
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
- Title not available (Why is that?)
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- Improved dynamic algorithms for maintaining approximate shortest paths under deletions
- 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
- Near linear time \((1 + \epsilon)\)-approximation for restricted shortest paths in undirected graphs
Cited In (16)
- Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs
- Dynamic approximate all-pairs shortest paths in undirected graphs
- Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
- Title not available (Why is that?)
- Improved dynamic algorithms for maintaining approximate shortest paths under deletions
- 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
- Approximating all-pair bounded-leg shortest path and APSP-AF in truly-subcubic time
- Title not available (Why is that?)
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
- A new deterministic algorithm for fully dynamic all-pairs shortest paths
- Deterministic incremental APSP with polylogarithmic update time and stretch
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
- 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)
