A Linear-Time Algorithm for Finding a Central Vertex of a Chordal Graph
A Linear-Time Algorithm for Finding a Central Vertex of a Chordal Graph
复制标题
寻找弦图中心顶点的线性时间算法
DOI：
10.1007/bfb0049406
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
F. Dragan
中科院分区：
文献类型：
--
作者：
V. Chepoi;F. Dragan
在图G =（V，E）中，顶点V的偏心率E（V）是最大{D（V，U）∶U∈V}。偏心率。 - 图表的时间测试弦。
In a graph G=(V, E), the eccentricity e(v) of a vertex v is max{d(v, u)∶u ∈ V}. The center of a graph is the set of vertices with minimum eccentricity. A graph G is chordal if every cycle of length at least four has a chord. We present an algorithm which computes in linear time a central vertex of a chordal graph. The algorithm uses the metric properties of chordal graphs and Tarjan and Yannakakis linear-time test for graph chordality.