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

An(ε,φ)-expander decomposition of a graph G=(V,E) is a clustering of the vertices V=V1∪…∪ Vx such that (1) each cluster Vi induces subgraph with conductance at least φ, and (2) the number of inter-cluster edges is at most ε|E|. In this paper, we give an improved distributed expander decomposition, and obtain a nearly optimal distributed triangle enumeration algorithm in the CONGEST model.Specifically, we construct an (ε,φ)-expander decomposition with φ=(ε/log n)2 O(k) in O(n2/k ⋅ poly (1/φ, log n))rounds for any ε ∈(0,1) and positive integer k. For example, a (1/no(1), 1/no(1))-expander decomposition only requires O(no(1)) rounds to compute, which is optimal up to subpolynomial factors, and a (0.01,1/poly log n)-expander decomposition can be computed in O(nγ) rounds, for any arbitrarily small constant γ > 0. Previously, the algorithm by Chang, Pettie, and Zhang can construct a (1/6,1/poly log n)-expander decomposition using Õ (n1-δ) rounds for any δ > 0, with a caveat that the algorithm is allowed to throw away a set of edges into an extra part which form a subgraph with arboricity at most nδ. Our algorithm does not have this caveat.By slightly modifying the distributed algorithm for routing on expanders by Ghaffari, Kuhn and Su [PODC'17], we obtain a triangle enumeration algorithm using Õ(n1/3) rounds. This matches the lower bound by Izumi and LeGall [PODC'17] and Pandurangan, Robinson and Scquizzato [SPAA'18] of Ø(n1/3) which holds even in the CONGESTED-CLIQUE model. To the best of our knowledge, this provides the first non-trivial example for a distributed problem that has essentially the same complexity (up to a polylogarithmic factor) in both CONGEST and CONGESTED-CLIQUE.The key technique in our proof is the first distributed approximation algorithm for finding a low conductance cut that is as balanced as possible. Previous distributed sparse cut algorithms do not have this nearly most balanced guarantee.

Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration