A subquadratic-time algorithm for decremental single-source shortest paths

DOI10.1137/1.9781611973402.79MaRDI QIDQ5384041zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

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

Cited in

(14)

• 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 partially dynamic single source shortest paths for sparse graphs
• Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound
• New tradeoffs for decremental approximate 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
• 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)