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(d\log 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)$.
翻译：中位图构成图表的类别, 该类别在图理中研究最多。 最近, B\'en\'eteau et al. [2019] 设计了一个线性算法, 计算$\ Theta$- class 和中位图的中位数组。 自然出现一个问题: 是否有线性时间算法, 计算中位图的直径和半径? 我们对此问题的答复是肯定的, 对于具有恒定维度的中位图来说, $G$, 即最大诱导超立方的维度为$G$。 我们提议一种组合式算法, 计算中位图的所有偏心值, 运行时间为$O( 2 ⁇ ⁇ ( d\ log d) n。 因此, 这为我们提供了一个线性算法, 确定中位图的直径和半径, $ = O(1) 美元, 如无立方体中位图, 我们对此问题的答复是肯定的。 由于第 4 度的超立方体不是规划的尺寸, 我们还表明, 计划中位中位中位图的所有电子中心值都可以以 $( $ ) 。
相关内容
微信扫码咨询专知VIP会员