Diameter, radius and all eccentricities in linear time for constant-dimension median graphs

MaRDI QIDQ6368528zbMATH OpenFDO

Authors Pierre Bergé, Michel Habib

Publication date 25 May 2021

Abstract: Median graphs form the class of graphs which is the most studied in metric graph theory. Recently, B'en'eteau et al. [2019] designed a linear-time algorithm computing both the $Theta$-classes and the median set of median graphs. A natural question emerges: is there a linear-time algorithm computing the diameter and the radius for median graphs? We answer positively to this question for median graphs $G$ with constant dimension $d$, i.e. the dimension of the largest induced hypercube of $G$. We propose a combinatorial algorithm computing all eccentricities of median graphs with running time $O(2^{O(dlogd)}n)$. As a consequence, this provides us with a linear-time algorithm determining both the diameter and the radius of median graphs with $d=O(1)$, such as cube-free median graphs. As the hypercube of dimension 4 is not planar, it shows also that all eccentricities of planar median graphs can be computed in $O(n)$.

This page was built for publication: Diameter, radius and all eccentricities in linear time for constant-dimension median graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6368528)