Additive Tree O(ρlog n)-Spanners from Tree Breadth ρ

2020/02/27 by Bendele, Oliver, Rautenbach, Dieter
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2002.12103

Abstract

The tree breadth \rm tb(G) of a connected graph G is the smallest non-negative integer ρ such that G has a tree decomposition whose bags all have radius at most ρ. We show that, given a connected graph G of order n and size m, one can construct in time O(mlog n) an additive tree O(\rm tb(G)log n)-spanner of G, that is, a spanning subtree T of G in which d_T(u,v)≤ d_G(u,v)+O(\rm tb(G)log n) for every two vertices u and v of G. This improves earlier results of Dragan and Köhler (Algorithmica 69 (2014) 884-905), who obtained a multiplicative error of the same order, and of Dragan and Abu-Ata (Theoretical Computer Science 547 (2014) 1-17), who achieved the same additive error with a collection of O(log n) trees.

Related

• Collective Additive Tree Spanners of Bounded Tree-Breadth Graphs with\n Generalizations and Consequences
• Lower bounds on collective additive spanners
• Additive Spanners: A Simple Construction
• Tree spanners of small diameter
• Sparsification Lower Bound for Linear Spanners in Directed Graphs