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

For a positive parameter $\beta$, the $\beta$-bounded distance between a pairof vertices $u,v$ in a weighted undirected graph $G = (V,E,\omega)$ is thelength of the shortest $u-v$ path in $G$ with at most $\beta$ edges, aka {\emhops}. For $\beta$ as above and $\epsilon>0$, a {\em $(\beta,\epsilon)$-hopset}of $G = (V,E,\omega)$ is a graph $G' =(V,H,\omega_H)$ on the same vertex set,such that all distances in $G$ are $(1+\epsilon)$-approximated by$\beta$-bounded distances in $G\cup G'$.  Hopsets are a fundamental graph-theoretic and graph-algorithmic construct,and they are widely used for distance-related problems in a variety ofcomputational settings. Currently existing constructions of hopsets producehopsets either with $\Omega(n \log n)$ edges, or with a hopbound$n^{\Omega(1)}$. In this paper we devise a construction of {\em linear-size}hopsets with hopbound $(\log n)^{\log^{(3)}n+O(1)}$. This improves the previousbound almost exponentially.  We also devise efficient implementations of our construction in PRAM anddistributed settings. The only existing PRAM algorithm \cite{EN16} forcomputing hopsets with a constant (i.e., independent of $n$) hopbound requires$n^{\Omega(1)}$ time. We devise a PRAM algorithm with polylogarithmic runningtime for computing hopsets with a constant hopbound, i.e., our running time isexponentially better than the previous one. Moreover, these hopsets are alsosignificantly sparser than their counterparts from \cite{EN16}.  We use our hopsets to devise a distributed routing scheme that exhibitsnear-optimal tradeoff between individual memory requirement$\tilde{O}(n^{1/k})$ of vertices throughout preprocessing and routing phases ofthe algorithm, and stretch $O(k)$, along with a near-optimal construction time$\approx D + n^{1/2 + 1/k}$, where $D$ is the hop-diameter of the input graph.

Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory