Earlier Version

Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks

Henzinger MH, Krinninger S, Nanongkai D. 2013. Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks. 40th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 7966, 607–619.

Download (ext.)

Conference Paper | Published | English

Scopus indexed
Author
Henzinger, MonikaISTA ; Krinninger, Sebastian; Nanongkai, Danupon
Series Title
LNCS
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 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 [9] that is optimal under some assumptions [27]. 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.
Publishing Year
Date Published
2013-07-01
Proceedings Title
40th International Colloquium on Automata, Languages, and Programming
Publisher
Springer Nature
Volume
7966
Page
607–619
Conference
ICALP: International Colloquium on Automata, Languages, and Programming
Conference Location
Riga, Latvia
Conference Date
2013-07-08 – 2013-07-12
ISSN
IST-REx-ID

Cite this

Henzinger MH, Krinninger S, Nanongkai D. Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks. In: 40th International Colloquium on Automata, Languages, and Programming. Vol 7966. Springer Nature; 2013:607–619. doi:10.1007/978-3-642-39212-2_53
Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2013). Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks. In 40th International Colloquium on Automata, Languages, and Programming (Vol. 7966, pp. 607–619). Riga, Latvia: Springer Nature. https://doi.org/10.1007/978-3-642-39212-2_53
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks.” In 40th International Colloquium on Automata, Languages, and Programming, 7966:607–619. Springer Nature, 2013. https://doi.org/10.1007/978-3-642-39212-2_53.
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks,” in 40th International Colloquium on Automata, Languages, and Programming, Riga, Latvia, 2013, vol. 7966, pp. 607–619.
Henzinger MH, Krinninger S, Nanongkai D. 2013. Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks. 40th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 7966, 607–619.
Henzinger, Monika H., et al. “Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks.” 40th International Colloquium on Automata, Languages, and Programming, vol. 7966, Springer Nature, 2013, pp. 607–619, doi:10.1007/978-3-642-39212-2_53.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 1512.08147

Search this title in

Google Scholar
ISBN Search