Maintaining shortest paths under deletions in weighted directed graphs

DOI10.1137/130938670MaRDI QIDQ2805514zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

shortest pathsapproximationgraph algorithmsdynamic algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Signed and weighted graphs (05C22) Paths and cycles (05C38)

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

Cites work

• scientific article; zbMATH DE number 1306899 (Why is no real title available?)
• A new approach to dynamic all pairs shortest paths
• An Incremental Algorithm for a Generalization of the Shortest-Path Problem
• An On-Line Edge-Deletion Problem
• Compact oracles for reachability and approximate distances in planar digraphs
• Computing and Combinatorics
• Dynamic approximate all-pairs shortest paths in undirected graphs
• Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
• Highway dimension, shortest paths, and provably efficient algorithms
• Improved Dynamic Reachability Algorithms for Directed Graphs
• Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
• Improved dynamic algorithms for maintaining approximate shortest paths under deletions
• Maintaining shortest paths under deletions in weighted directed graphs
• Near linear time \((1 + \epsilon)\)-approximation for restricted shortest paths in undirected graphs
• On dynamic shortest paths problems
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs

Cited in

(16)

• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• 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
• scientific article; zbMATH DE number 2086658 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 2079363 (Why is no real title available?)
• 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

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)