Maxstretch reduction for tree spanners
Research output: Contribution to journal › Article
Abstract
A tree tspanner T of a graph G is a spanning tree of G whose maxstretch is t, i.e., the distance between any two vertices in T is at most t times their distance in G. If G has a tree tspanner but not a tree (t−1)spanner, then G is said to have maxstretch of t. In this paper, we study the MaxStretch Reduction Problem: for an unweighted graph G=(V,E), find a set of edges not in E originally whose insertion into G can decrease the maxstretch of G. Our results are as follows: (i) For a ring graph, we give a lineartime algorithm which inserts k edges improving the maxstretch optimally. (ii) For a grid graph, we give a nearly optimal maxstretch reduction algorithm which preserves the structure of the grid. (iii) In the general case, we show that it is $mathcal{NP}$ hard to decide, for a given graph G and its spanning tree of maxstretch t, whether or not oneedge insertion can decrease the maxstretch to t−1. (iv) Finally, we show that the maxstretch of an arbitrary graph on n vertices can be reduced to s′≥2 by inserting O(n/s′) edges, which can be determined in linear time, and observe that this number of edges is optimal up to a constant.
Details
Authors  

Research areas and keywords  Subject classification (UKÄ) – MANDATORY

Original language  English 

Pages (fromto)  223235 
Journal  Algorithmica 
Volume  50 
Issue number  2 
State  Published  2008 
Peerreviewed  Yes 