Logo der Universität Wien

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.

Grafik Top
Paper in Conference Proceedings or in Workshop Proceedings (Full Paper in Proceedings)
Event Title
40th International Colloquium on Automata, Languages and Programming (ICALP 2013)
Theory and Applications of Algorithms
Theoretische Informatik
Event Location
Riga, Latvia
Event Type
Event Dates
8-12 July 2013
Series Name
Automata, Languages, and Programming, 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II
Page Range
pp. 607-619
July 2013
Grafik Top
Contact us
Faculty of Computer Science
University of Vienna

Währinger Straße 29
A-1090 Vienna