Diameter, radius and all eccentricities in linear time for constant-dimension median graphs
share
Median graphs form the class of graphs which is the most studied in metric graph theory. Recently, Bénéteau et al. [2019] designed a linear-time algorithm computing both the Θ-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(dlog d)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).
READ FULL TEXT