Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time

DOI10.1145/3218657zbMath1426.68215arXiv1512.08148OpenAlexW2900627138MaRDI QIDQ4625657

Danupon Nanongkai, Sebastian Krinninger, Monika R. Henzinger

Publication date: 25 February 2019

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

approximate shortest pathshop sets

Mathematics Subject Classification ID

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

Related Items (8)

Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Unnamed Item ⋮ Fast approximate shortest paths in the congested clique ⋮ Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC ⋮ Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time

This page was built for publication: Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time