距离 - 遗传图中的偏心函数

作者：Feodor F. Dragan,Heather M. Guarnera

摘要：如果G的每个诱导路径都是最短路径，则图G =（V，E）是距离遗传。 在本文中，我们证明了任何距离 - 遗传图中的偏心函数（v）= max {d（v，u）：u∈V}几乎是单峰的，即每个顶点（v）> rad（G）+ 1有一个偏心较小的邻居。 这里，rad（G）= min {e（v）：v∈V}是graphG的半径。 此外，我们使用该结果来表征距离 - 遗传图的中心，并提供线性时间算法以找到大的中心顶点子集，并且在一些情况下，所有中心顶点。 我们引入了两种新的算法技术来逼近距离 - 遗传图中的所有偏心率，包括线性时间加法1近似。

原文标题：Eccentricity function in distance-hereditary graphs

原文摘要：A graphG=(V,E)is distance hereditary if every induced path ofGis a shortest path. In this paper, we show that the eccentricity functione(v)=max{d(v,u):u∈V}in any distance-hereditary graphGis almost unimodal, that is, every vertexvwithe(v)>rad(G)+1has a neighbor with smaller eccentricity. Here,rad(G)=min{e(v):v∈V}is the radius of graphG. Moreover, we use this result to characterize the centers of distance-hereditary graphs and provide a linear time algorithm to find a large subset of central vertices, and in some cases, all central vertices. We introduce two new algorithmic techniques to approximate all eccentricities in distance-hereditary graphs, including a linear time additive 1-approximation.

地址：https://arxiv.org/abs/1907.05445