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

Consider an undirected weighted graph G=(V,E) with |V|=n and |E|=m, where each vertex v∈V is assigned a label from a set of labels L={λ1,...,λℓ}. We show how to construct a compact distance oracle that can answer queries of the form: "what is the distance from v to the closest λ-labeled vertex" for a given vertex v∈V and label λ∈L. This problem was introduced by Hermelin, Levy, Weimann and Yuster [ICALP 2011] where they present several results for this problem. In the first result, they show how to construct a vertex-label distance oracle of expected size O(kn1+1/k) with stretch (4k−5) and query time O(k). In a second result, they show how to reduce the size of the data structure to O(kn ℓ1/k) at the expense of a huge stretch, the stretch of this construction grows exponentially in k, (2k−1). In the third result they present a dynamic vertex-label distance oracle that is capable of handling label changes in a sub-linear time. The stretch of this construction is also exponential in k, (2·3k−1+1). We manage to significantly improve the stretch of their constructions, reducing the dependence on k from exponential to polynomial (4k−5), without requiring any tradeoff regarding any of the other variables. In addition, we introduce the notion of vertex-label spanners: subgraphs that preserve distances between every vertex v∈V and label λ∈L. We present an efficient construction for vertex-label spanners with stretch-size tradeoff close to optimal.

Improved Distance Oracles and Spanners for Vertex-Labeled Graphs