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

We consider how to assign labels to any undirected graph with n nodes suchthat, given the labels of two nodes and no other information regarding thegraph, it is possible to determine the distance between the two nodes. Thechallenge in such a distance labeling scheme is primarily to minimize themaximum label lenght and secondarily to minimize the time needed to answerdistance queries (decoding). Previous schemes have offered different trade-offsbetween label lengths and query time. This paper presents a simple algorithmwith shorter labels and shorter query time than any previous solution, therebyimproving the state-of-the-art with respect to both label length and query timein one single algorithm. Our solution addresses several open problemsconcerning label length and decoding time and is the first improvement of labellength for more than three decades.  More specifically, we present a distance labeling scheme with label size (log3)/2 + o(n) (logarithms are in base 2) and O(1) decoding time. This outperformsall existing results with respect to both size and decoding time, includingWinkler's (Combinatorica 1983) decade-old result, which uses labels of size(log 3)n and O(n/log n) decoding time, and Gavoille et al. (SODA'01), whichuses labels of size 11n + o(n) and O(loglog n) decoding time. In addition, ouralgorithm is simpler than the previous ones. In the case of integral edgeweights of size at most W, we present almost matching upper and lower boundsfor label sizes. For r-additive approximation schemes, where distances can beoff by an additive constant r, we give both upper and lower bounds. Inparticular, we present an upper bound for 1-additive approximation schemeswhich, in the unweighted case, has the same size (ignoring second order terms)as an adjacency scheme: n/2. We also give results for bipartite graphs and forexact and 1-additive distance oracles.

Simpler, faster and shorter labels for distances in graphs