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

摘要

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.