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

On sparse graphs, Roditty and Williams [2013] proved that no$O(n^{2-\varepsilon})$-time algorithm achieves an approximation factor smallerthan $\frac{3}{2}$ for the diameter problem unless SETH fails. In this article,we solve an open question formulated in the literature: can we use thestructural properties of median graphs to break this global quadratic barrier?  We propose the first combinatiorial algorithm computing exactly alleccentricities of a median graph in truly subquadratic time. Median graphsconstitute the family of graphs which is the most studied in metric graphtheory because their structure represents many other discrete and geometricconcepts, such as CAT(0) cube complexes. Our result generalizes a recent one,stating that there is a linear-time algorithm for all eccentricities in mediangraphs with bounded dimension $d$, i.e. the dimension of the largest inducedhypercube. This prerequisite on $d$ is not necessarily anymore to determine alleccentricities in subquadratic time. The execution time of our algorithm is$O(n^{1.6408}\log^{O(1)} n)$.  We provide also some satellite outcomes related to this general result. Inparticular, restricted to simplex graphs, this algorithm enumerates alleccentricities with a quasilinear running time. Moreover, an algorithm isproposed to compute exactly all reach centralities in time$O(2^{3d}n\log^{O(1)}n)$.

Subquadratic-time algorithm for the diameter and all eccentricities on median graphs