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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

A partition C1,C2,...,Cq of G=V,E into clusters of strong respectively, weak diameter d, such that the supergraph obtained by contracting each Ci is ℓ-colorable is called a strong resp., weak d, ℓ-network-decomposition. Network-decompositions were introduced in a seminal paper by Awerbuch, Goldberg, Luby and Plotkin in 1989. Awerbuch et al. showed that strong $exp\\{O\\sqrt{ \\log n \\log \\log n}\\}$, $exp\\{O\\sqrt{ \\log n \\log \\log n}\\}$-network-decompositions can be computed in distributed deterministic time $exp\\{O\\sqrt{ \\log n \\log \\log n}\\}$. Even more importantly, they demonstrated that network-decompositions can be used for a great variety of applications in the message-passing model of distributed computing. Much more recently Barenboim 2012 devised a distributed randomized constant-time algorithm for computing strong network decompositions with d=O1. However, the parameter ℓ in his result is On1/2+ε. In this paper we drastically improve the result of Barenboim and devise a distributed randomized constant-time algorithm for computing strong O1, Onε-network-decompositions. As a corollary we derive a constant-time randomized Onε-approximation algorithm for the distributed minimum coloring problem. This improves the best previously-known On1/2+ε approximation guarantee. We also derive other improved distributed algorithms for a variety of problems. Most notably, for the extremely well-studied distributed minimum dominating set problem currently there is no known deterministic polylogarithmic -time algorithm. We devise a deterministic polylogarithmic-time approximation algorithm for this problem, addressing an open problem of Lenzen and Wattenhofer 2010.

A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation