Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks

DOI10.1145/3146550zbMath1452.68269arXiv1512.08147OpenAlexW24636605MaRDI QIDQ4554941

Sebastian Krinninger, Danupon Nanongkai, Monika R. Henzinger

Publication date: 12 November 2018

Published in: ACM Transactions on Algorithms, Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

distributed algorithmsdynamic algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items

Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization