Easy computation of eccentricity approximating trees

被引:4
作者
Ducoffe, Guillaume [1 ,2 ,3 ]
机构
[1] Natl Inst Res & Dev Informat, Bucharest, Romania
[2] Univ Bucharest, Fac Math & Comp Sci, Bucharest, Romania
[3] Univ Bucharest ICUB, Res Inst, Bucharest, Romania
关键词
Eccentricity-approximating tree; Shortest-path tree; Complexity; Graph algorithms;
D O I
10.1016/j.dam.2019.01.006
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A spanning tree T of a graph G = (V, E) is called eccentricity k-approximating if we have ecc(T)(v) <= ecc(G) (v) + k for every v is an element of V. Let ets(G) be the minimum k such that G admits an eccentricity k-approximating spanning tree. As our main contribution in this paper, we prove that ets(G) can be computed in O(nm)-time along with a corresponding spanning tree. This answers an open question of Dragan et al. (2017). Moreover we also prove that for some classes of graphs such as chordal graphs and hyperbolic graphs, one can compute an eccentricity O(ets(G))-approximating spanning tree in quasi linear time. Our proofs are based on simple relationships between eccentricity approximating trees and shortest-path trees. (C) 2019 Elsevier B.V. All rights reserved.
引用
收藏
页码:267 / 271
页数:5
相关论文
共 19 条
[1]  
BONDY J. A., 2008, GRAD TEXTS MATH
[2]   Distance approximating trees for chordal and dually chordal graphs [J].
Brandstädt, A ;
Chepoi, V ;
Dragan, F .
JOURNAL OF ALGORITHMS, 1999, 30 (01) :166-184
[3]   GRAPHS WITH ALL DIAMETRAL PATHS THROUGH DISTANT CENTRAL NODES [J].
BUCKLEY, F ;
LEWINTER, M .
MATHEMATICAL AND COMPUTER MODELLING, 1993, 17 (11) :35-41
[4]   Finding a central vertex in an HHD-free graph [J].
Chepoi, V ;
Dragan, F .
DISCRETE APPLIED MATHEMATICS, 2003, 131 (01) :93-111
[5]  
Chepoi V., 2018, COCOA
[6]   Diameters, Centers, and Approximating Trees of δ-Hyperbolic Geodesic Spaces and Graphs [Extended Abstract] [J].
Chepoi, Victor ;
Dragan, Feodor F. ;
Estellon, Bertrand ;
Habib, Michel ;
Vaxes, Yann .
PROCEEDINGS OF THE TWENTY-FOURTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SGG'08), 2008, :59-68
[7]  
Corneil DG, 2005, LECT NOTES COMPUT SC, V3787, P151
[8]  
Demmer MJ, 1998, LECT NOTES COMPUT SC, V1499, P119, DOI 10.1007/BFb0056478
[9]   Eccentricity approximating trees [J].
Dragan, Feodor F. ;
Koehler, Ekkehard ;
Alrasheed, Hend .
DISCRETE APPLIED MATHEMATICS, 2017, 232 :142-156
[10]   Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences [J].
Dragan, Feodor F. ;
Abu-Ata, Muad .
THEORETICAL COMPUTER SCIENCE, 2014, 547 :1-17