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

DOI10.1145/3146550zbMath1452.68269arXiv1512.08147MaRDI 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 algorithms; dynamic algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68W25: Approximation algorithms

68W15: Distributed algorithms