Deterministic partially dynamic single source shortest paths for sparse graphs

DOI10.1137/1.9781611974782.29MaRDI QIDQ4575766zbMATH OpenOpenAlexFDO

Authors Aaron Bernstein, Shiri Chechik

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.29

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Distance in graphs (05C12)

Recommendations

• Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound
• scientific article; zbMATH DE number 7204496
• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
• A subquadratic-time algorithm for decremental single-source shortest paths
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs

Cited in

(10)

• Simple dynamic spanners with near-optimal recourse against an adaptive adversary
• scientific article; zbMATH DE number 7204496 (Why is no real title available?)
• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• 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
• A subquadratic-time algorithm for decremental single-source shortest paths
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization

This page was built for publication: Deterministic partially dynamic single source shortest paths for sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575766)