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

In a sequence of recent results (PODC 2015 and PODC 2016), the running timeof the fastest algorithm for the \emph{minimum spanning tree (MST)} problem inthe \emph{Congested Clique} model was first improved to $O(\log \log \log n)$from $O(\log \log n)$ (Hegeman et al., PODC 2015) and then to $O(\log^* n)$(Ghaffari and Parter, PODC 2016). All of these algorithms use $\Theta(n^2)$messages independent of the number of edges in the input graph.  This paper positively answers a question raised in Hegeman et al., andpresents the first "super-fast" MST algorithm with $o(m)$ message complexityfor input graphs with $m$ edges. Specifically, we present an algorithm runningin $O(\log^* n)$ rounds, with message complexity $\tilde{O}(\sqrt{m \cdot n})$and then build on this algorithm to derive a family of algorithms, containingfor any $\varepsilon$, $0 < \varepsilon \le 1$, an algorithm running in$O(\log^* n/\varepsilon)$ rounds, using $\tilde{O}(n^{1 +\varepsilon}/\varepsilon)$ messages. Setting $\varepsilon = \log\log n/\log n$leads to the first sub-logarithmic round Congested Clique MST algorithm thatuses only $\tilde{O}(n)$ messages.  Our primary tools in achieving these results are (i) a component-wise boundon the number of candidates for MST edges, extending the sampling lemma ofKarger, Klein, and Tarjan (Karger, Klein, and Tarjan, JACM 1995) and (ii)$\Theta(\log n)$-wise-independent linear graph sketches (Cormode and Firmani,Dist.~Par.~Databases, 2014) for generating MST candidate edges.

Super-fast MST Algorithms in the Congested Clique using $o(m)$ Messages