A subquadratic-time algorithm for decremental single-source shortest paths
DOI10.1137/1.9781611973402.79zbMATH Open1421.68231OpenAlexW4256186298MaRDI QIDQ5384041FDOQ5384041
Authors: Sebastian Krinninger, Danupon Nanongkai, Monika R. Henzinger 
Publication date: 20 June 2019
Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/1.9781611973402.79
Recommendations
- Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- Improved dynamic algorithms for maintaining approximate shortest paths under deletions
- Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound
- Deterministic partially dynamic single source shortest paths for sparse graphs
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Data structures (68P05) Approximation algorithms (68W25) Paths and cycles (05C38)
Cited In (13)
- Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
- Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
- Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
- Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
- A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
- Improved dynamic algorithms for maintaining approximate shortest paths under deletions
- Computing and Combinatorics
- Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound
- Deterministic partially dynamic single source shortest paths for sparse graphs
- Deterministic incremental APSP with polylogarithmic update time and stretch
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- Incremental single-source shortest paths in digraphs with arbitrary positive arc weights
This page was built for publication: A subquadratic-time algorithm for decremental single-source shortest paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384041)
