Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS. University of Vienna, Austria.
2017 (English)In: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 13, no 4, article id 51Article in journal (Refereed) Published
Abstract [en]

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 + is an element of)-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 + is an element of)-approximate incremental algorithm for single-source shortest paths in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic exact algorithm of Even and Shiloach (1981), which is optimal under some assumptions (Roditty and Zwick 2011; Henzinger et al. 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.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2017. Vol. 13, no 4, article id 51
Keywords [en]
Distributed algorithms, dynamic algorithms
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-221380DOI: 10.1145/3146550ISI: 000419242000008Scopus ID: 2-s2.0-85041442206OAI: oai:DiVA.org:kth-221380DiVA, id: diva2:1174957
Funder
EU, FP7, Seventh Framework Programme, 317532; 340506
Note

QC 20180117

Available from: 2018-01-17 Created: 2018-01-17 Last updated: 2018-01-29Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Nanongkai, Danupon
By organisation
Theoretical Computer Science, TCS
In the same journal
ACM Transactions on Algorithms
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 7 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf