Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks
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 show (1+ε)-approximation algorithms whose amortized time (over some number of link changes) is sublinear in D, the maximum diameter of the network. This breaks the Θ(D) time bound of recomputing “from scratch”. Our technique also leads to a (1+ε)-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). Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if a small approximation is allowed.
|Paper in Conference Proceedings or in Workshop Proceedings (Full Paper in Proceedings)|
|40th International Colloquium on Automata, Languages and Programming (ICALP 2013)|
|Theory and Applications of Algorithms|
|8-12 July 2013|
|Automata, Languages, and Programming, 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II|