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

Hyperbolicity is a graph parameter which indicates how much the shortest-pathdistance metric of a graph deviates from a tree metric. It is used in variousfields such as networking, security, and bioinformatics for the classificationof complex networks, the design of routing schemes, and the analysis of graphalgorithms. Despite recent progress, computing the hyperbolicity of a graphremains challenging. Indeed, the best known algorithm has time complexity$O(n^{3.69})$, which is prohibitive for large graphs, and the most efficientalgorithms in practice have space complexity $O(n^2)$. Thus, time as well asspace are bottlenecks for computing hyperbolicity.  In this paper, we design a tool for enumerating all far-apart pairs of agraph by decreasing distances. A node pair $(u, v)$ of a graph is far-apart ifboth $v$ is a leaf of all shortest-path trees rooted at $u$ and $u$ is a leafof all shortest-path trees rooted at $v$. This notion was previously used todrastically reduce the computation time for hyperbolicity in practice. However,it required the computation of the distance matrix to sort all pairs of nodesby decreasing distance, which requires an infeasible amount of memory alreadyfor medium-sized graphs. We present a new data structure that avoids thismemory bottleneck in practice and for the first time enables computing thehyperbolicity of several large graphs that were far out-of-reach using previousalgorithms. For some instances, we reduce the memory consumption by at leasttwo orders of magnitude. Furthermore, we show that for many graphs, only a verysmall fraction of far-apart pairs have to be considered for the hyperbolicitycomputation, explaining this drastic reduction of memory.  As iterating over far-apart pairs in decreasing order without storing themexplicitly is a very general tool, we believe that our approach might also berelevant to other problems.

Enumeration of Far-Apart Pairs by Decreasing Distance for Faster Hyperbolicity Computation