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

A distance oracle is a compact representation of the shortest distance matrixof a graph. It can be queried to approximate shortest paths between any pair ofvertices. Any distance oracle that returns paths of worst-case stretch (2k-1)must require space $\Omega(n^{1 + 1/k})$ for graphs of n nodes. The hard casesthat enforce this lower bound are, however, rather dense graphs with averagedegree \Omega(n^{1/k}).  We present distance oracles that, for sparse graphs, substantially break thelower bound barrier at the expense of higher query time. For any 1 \leq \alpha\leq n, our distance oracles can return stretch 2 paths using O(m + n^2/\alpha)space and stretch 3 paths using O(m + n^2/\alpha^2) space, at the expense ofO(\alpha m/n) query time. By setting appropriate values of \alpha, we get thefirst distance oracles that have size linear in the size of the graph, andreturn constant stretch paths in non-trivial query time. The query time can befurther reduced to O(\alpha), by using an additional O(m \alpha) space for allour distance oracles, or at the cost of a small constant additive stretch.  We use our stretch 2 distance oracle to present the first compact routingscheme with worst-case stretch 2. Any compact routing scheme with stretch lessthan 2 must require linear memory at some nodes even for sparse graphs; ourscheme, hence, achieves the optimal stretch with non-trivial memoryrequirements. Moreover, supported by large-scale simulations on graphsincluding the AS-level Internet graph, we argue that our stretch-2 scheme wouldbe simple and efficient to implement as a distributed compact routing protocol.

Faster Approximate Distance Queries and Compact Routing in Sparse Graphs