Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary

DOI10.1137/1.9781611975994.155MaRDI QIDQ5146946zbMATH 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.10821

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Faster cut sparsification of weighted graphs
• The power of vertex sparsifiers in dynamic graph algorithms
• Approximation algorithms for the weighted independent set problem in sparse graphs
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
• Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound
• Adaptive majority problems for restricted query graphs and for weighted sets
• A subquadratic-time algorithm for decremental single-source shortest paths
• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• Decremental all-pairs shortest paths in deterministic near-linear time

Cited in

(4)

• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Decremental strongly connected components and single-source reachability in near-linear time
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Simple dynamic spanners with near-optimal recourse against an adaptive adversary

This page was built for publication: Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary

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