English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the problem of maintaining a breadth-first spanning tree (BFS tree)in partially dynamic distributed networks modeling a sequence of eitherfailures or additions of communication links (but not both). We presentdeterministic $(1+\epsilon)$-approximation algorithms whose amortized time(over some number of link changes) is sublinear in $D$, the maximum diameter ofthe network.  Our technique also leads to a deterministic $(1+\epsilon)$-approximateincremental algorithm for single-source shortest paths (SSSP) in the sequential(usual RAM) model. Prior to our work, the state of the art was the classicexact algorithm of Even and Shiloach [JACM 1981] that is optimal under someassumptions [Roditty and Zwick ESA 2004, Henzinger et al. STOC 2015]. Ourresult is the first to show that, in the incremental setting, this bound can bebeaten in certain cases if some approximation is allowed.Comment: A preliminary version of this paper appeared in the International  Colloquium on Automata, Languages and Programming (ICALP) 201

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