An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time

作     者：Dragan, Feodor F. 

作者机构：Kent State Univ Dept Comp Sci Algorithm Res Lab Kent OH 44242 USA 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2020年第154卷

页      面：105873-000页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Linear-time algorithm Chordal graphs Eccentricities Approximation Spanning trees 

摘      要：It is known that every chordal graph G = (V, E) has a spanning tree T such that, for every vertex v e V, eccG(v) eccG(v) + 2 holds (here eccG(v) := max{dG(v, u) : u E V} is the eccentricity of v in G). We show that such a spanning tree can be computed in linear time for every chordal graph. As a byproduct, we get that the eccentricities of all vertices of a chordal graph G can be computed in linear time with an additive one-sided error of at most 2, i.e., after a linear time preprocessing, for every vertex v of G, one can compute in 0(1) time an estimate e(v) of its eccentricity eccG(v) such that eccG(v) e(v) eccG(v) + 2. (C) 2019 Elsevier B.V. All rights reserved.