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

Graph spanners are sparse subgraphs that faithfully preserve the distances inthe original graph up to small stretch. Spanner have been studied extensivelyas they have a wide range of applications ranging from distance oracles,labeling schemes and routing to solving linear systems and spectralsparsification. A $k$-spanner maintains pairwise distances up to multiplicativefactor of $k$. It is a folklore that for every $n$-vertex graph $G$, one canconstruct a $(2k-1)$ spanner with $O(n^{1+1/k})$ edges. In a distributedsetting, such spanners can be constructed in the standard CONGEST model using$O(k^2)$ rounds, when randomization is allowed.  In this work, we consider spanner constructions in the congested cliquemodel, and show: (1) A randomized construction of a $(2k-1)$-spanner with$\widetilde{O}(n^{1+1/k})$ edges in $O(\log k)$ rounds. The previous bestalgorithm runs in $O(k)$ rounds. (2) A deterministic construction of a$(2k-1)$-spanner with $\widetilde{O}(n^{1+1/k})$ edges in $O(\log k +(\log\logn)^3)$ rounds. The previous best algorithm runs in $O(k\log n)$ rounds. Thisimprovement is achieved by a new derandomization theorem for hitting sets whichmight be of independent interest. (3) A deterministic construction of a$O(k)$-spanner with $O(k \cdot n^{1+1/k})$ edges in $O(\log k)$ rounds.

Congested Clique Algorithms for Graph Spanners