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. Motivated by previous work on dually chordalgraphs and graphs of bounded distance VC-dimension we prove several new resultson the complexity of computing the diameter and the radius on Helly graphs andrelated graph classes.  * First, we present algorithms which given an $n$-vertex $m$-edge Helly graph$G$ as input, compute w.h.p. its radius and its diameter in time $\tilde{\calO}(m\sqrt{n})$. Our algorithms are based on the Helly property and on severalimplications of the unimodality of the eccentricity function in Helly graphs:every vertex of locally minimum eccentricity is a central vertex.  * Then, we focus on $C_4$-free Helly graphs, which include, amongst othersubclasses, bridged Helly graphs and so, chordal Helly graphs and hereditaryHelly graphs. For the $C_4$-free Helly graphs, we present linear-timealgorithms for computing the eccentricity of all vertices. Doing so, wegeneralize previous results on strongly chordal graphs to a much largersubclass.  * Finally, we derive from our findings on chordal Helly graphs a more generalone-to-many reduction from diameter computation on chordal graphs to eitherdiameter computation on split graphs or the {\sc Disjoint Set} problem.Therefore, split graphs are in some sense the {\em only} hard instances fordiameter computation on chordal graphs. As a byproduct of our reduction theeccentricity of all vertices in a chordal graph can be approximated in ${\calO}(m\log{n})$ time with an additive one-sided error of at most one, and on anysubclass of chordal graphs with constant VC-dimension the diameter can becomputed in truly subquadratic time.  These above results are a new step toward better understanding the role ofabstract geometric properties in the fast computation of metric graphinvariants.

A story of diameter, radius and Helly property