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

Abstract

We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We present deterministic $(1+\epsilon )$-approximation algorithms whose amortized time (over some number of link changes) is sublinear in $D$, the maximum diameter of the network. Our technique also leads to a deterministic $(1+\epsilon )$-approximate incremental algorithm for single-source shortest paths (SSSP) in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic exact algorithm of Even and Shiloach [JACM 1981] that is optimal under some assumptions [Roditty and Zwick ESA 2004, Henzinger et al. STOC 2015]. Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if some approximation is allowed.

This article appears in ACM Transactions on Algorithms 13.4 (2017), pp 51:1-51:24, doi:10.1145/3146550. A preliminary version of this paper was presented at the 40th International Colloquium on Automata, Languages and Programming (ICALP 2013)

References in corpus (3)

• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
• Tight Bounds for Distributed Minimum-Weight Spanning Tree Verification