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

A graph is Helly if every family of pairwise intersecting balls has anonempty common intersection. The class of Helly graphs is the discreteanalogue of the class of hyperconvex metric spaces. It is also known that everygraph isometrically embeds into a Helly graph, making the latter an importantclass of graphs in Metric Graph Theory. We study diameter, radius and alleccentricity computations within the Helly graphs. Under plausible complexityassumptions, neither the diameter nor the radius can be computed in trulysubquadratic time on general graphs. In contrast to these negative results, itwas recently shown that the radius and the diameter of an $n$-vertex $m$-edgeHelly graph $G$ can be computed with high probability in $\tilde{\mathcalO}(m\sqrt{n})$ time (i.e., subquadratic in $n+m$). In this paper, we improvethat result by presenting a deterministic ${\mathcal O}(m\sqrt{n})$ timealgorithm which computes not only the radius and the diameter but also allvertex eccentricities in a Helly graph. Furthermore, we give a parameterizedlinear-time algorithm for this problem on Helly graphs, with the parameterbeing the Gromov hyperbolicity $\delta$. More specifically, we show that theradius and a central vertex of an $m$-edge $\delta$-hyperbolic Helly graph $G$can be computed in $\mathcal O(\delta m)$ time and that all vertexeccentricities in $G$ can be computed in $\mathcal O(\delta^2 m)$ time. To showthis more general result, we heavily use our new structural properties obtainedfor Helly graphs.

Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs