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

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present a distributed randomized algorithm finding Minimum Spanning Tree(MST) of a given graph in O(1) rounds, with high probability, in the CongestedClique model. The input graph in the Congested Clique model is a graph of nnodes, where each node initially knows only its incident edges. Thecommunication graph is a clique with limited edge bandwidth: each two nodes(not necessarily neighbours in the input graph) can exchange $O(\log n)$ bits.  As in previous works, the key part of the MST algorithm is an efficientConnected Components (CC) algorithm. However, unlike the former approaches, wedo not aim at simulating the standard Boruvka algorithm, at least at initialstages of the CC algorithm. Instead, we develop a new technique which combinesconnected components of sample sparse subgraphs of the input graph in order toaccelerate the process of uncovering connected components of the original inputgraph. More specifically, we develop a sparsification technique which reducesan initial CC problem in $O(1)$ rounds to its two restricted instances. Theformer instance has a graph with maximal degree $O(\log \log n)$ as the input-- here our sample-combining technique helps. In the latter instance, apartition of the input graph into $O(n/\log \log n)$ connected components isknown. This gives an opportunity to apply previous algorithms to determineconnected components in $O(1)$ rounds.  Our result addresses the problem from and the $O(\log \log n)$ algorithm ofLotker et al. [SPAA 2003; SICOMP 2005], improves over previous $O(\log* n)$algorithm of Ghaffari et al. [PODC 2016] and $O(\log \log \log n)$ algorithm ofHegeman et al. [PODC 2015] . It also determines $\Theta(1)$ round complexity inthe congested clique for MST, as well as other graph problems, includingbipartiteness, cut verification, s-t connectivity and cycle containment.

MST in O(1) Rounds of the Congested Clique