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

The \emph{Steiner tree} problem is one of the fundamental and classicalproblems in combinatorial optimization. In this paper, we study this problem inthe $\mathcal{CONGESTED}$ $\mathcal{CLIQUE}$ model of distributed computing andpresent two deterministic distributed approximation algorithms for the same.The first algorithm computes a Steiner tree in $\tilde{O}(n^{1/3})$ rounds and$\tilde{O}(n^{7/3})$ messages for a given connected undirected weighted graphof $n$ nodes. Note here that $\tilde{O}(\cdot)$ notation hides polylogarithmicfactors in $n$. The second one computes a Steiner tree in $O(S + \log\log n)$rounds and $O(S (n - t)^2 + n^2)$ messages, where $S$ and $t$ are the\emph{shortest path diameter} and the number of \emph{terminal} nodesrespectively in the given input graph. Both the algorithms admit anapproximation factor of $2(1 - 1/\ell)$, where $\ell$ is the number of terminalleaf nodes in the optimal Steiner tree. For graphs with $S = \omega(n^{1/3}\log n)$, the first algorithm exhibits better performance than the second onein terms of the round complexity. On the other hand, for graphs with $S =\tilde{o}(n^{1/3})$, the second algorithm outperforms the first one in terms ofthe round complexity. In fact when $S = O(\log\log n)$ then the secondalgorithm admits a round complexity of $O(\log\log n)$ and message complexityof $\tilde{O}(n^2)$. To the best of our knowledge, this is the first work tostudy the Steiner tree problem in the $\mathcal{CONGESTED}$ $\mathcal{CLIQUE}$model.

Distributed Approximation Algorithms for Steiner Tree in the $\mathcal{CONGESTED}$ $\mathcal{CLIQUE}$