Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler

DOI10.1137/1.9781611975994.154MaRDI QIDQ5146945zbMATH OpenOpenAlexFDO

Authors Maximilian Probst Gutenberg, Christian Wulff-Nilsen

Publication date 2 February 2021

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

Full work available at URL https://arxiv.org/abs/2001.10809

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(12)

• Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Fixed-parameter tractable algorithms for tracking shortest paths
• Polylog-time and near-linear work approximation scheme for undirected shortest paths
• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• A new deterministic algorithm for fully dynamic all-pairs shortest paths
• Simple dynamic spanners with near-optimal recourse against an adaptive adversary
• Fully dynamic algorithms for minimum weight cycle and related problems
• Approximation algorithms for optimal hopsets
• Incremental approximate single-source shortest paths with predictions

This page was built for publication: Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler

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