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

Hub labeling schemes are popular methods for computing distances on roadnetworks and other large complex networks, often answering to a query within afew microseconds for graphs with millions of edges. In this work, we studytheir algorithmic applications beyond distance queries. We focus oneccentricity queries and distance-sum queries, for several versions of theseproblems on directed weighted graphs, that is in part motivated by theirimportance in facility location problems. On the negative side, we showconditional lower bounds for these above problems on unweighted undirectedsparse graphs, via standard constructions from "Fine-grained" complexity.However, things take a different turn when the hub labels have a sublogarithmicsize. Indeed, given a hub labeling of maximum label size $\leq k$, afterpre-processing the labels in total $2^{{O}(k)} \cdot |V|^{1+o(1)}$ time, we cancompute both the eccentricity and the distance-sum of any vertex in $2^{{O}(k)}\cdot |V|^{o(1)}$ time. It can also be applied to the fast global computationof some topological indices. Finally, as a by-product of our approach, on anyfixed class of unweighted graphs with bounded expansion, we can decide whetherthe diameter of an $n$-vertex graph in the class is at most $k$ in $f(k) \cdotn^{1+o(1)}$ time, for some "explicit" function $f$.

Eccentricity queries and beyond using Hub Labels