Decremental strongly-connected components and single-source reachability in near-linear time

DOI10.1145/3313276.3316335zbMath1433.68637arXiv1901.03615OpenAlexW2964023274MaRDI QIDQ5212778

Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

dynamic algorithmstrongly connected componentssingle source reachability

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Beyond the BEST theorem: fast assessment of Eulerian trails, Fine-grained complexity lower bounds for problems in computer aided verification, Unnamed Item, Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs., Unnamed Item, Single-source shortest paths and strong connectivity in dynamic planar graphs