Maxstretch reduction for tree spanners
(2008) In Algorithmica 50(2). p.223235 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... (More)
 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. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/629545
 author
 Iwama, Kazuo; Lingas, Andrzej ^{LU} and Okita, Masaki
 organization
 publishing date
 2008
 type
 Contribution to journal
 publication status
 published
 subject
 in
 Algorithmica
 volume
 50
 issue
 2
 pages
 223  235
 publisher
 Springer
 external identifiers

 wos:000252190700004
 scopus:38149111914
 ISSN
 01784617
 DOI
 10.1007/s004530079058x
 project
 VR 20054085
 language
 English
 LU publication?
 yes
 id
 9521794ff6ba4f828fc86cef334ce517 (old id 629545)
 date added to LUP
 20071127 14:39:31
 date last changed
 20180529 11:28:45
@article{9521794ff6ba4f828fc86cef334ce517, 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.}, author = {Iwama, Kazuo and Lingas, Andrzej and Okita, Masaki}, issn = {01784617}, language = {eng}, number = {2}, pages = {223235}, publisher = {Springer}, series = {Algorithmica}, title = {Maxstretch reduction for tree spanners}, url = {http://dx.doi.org/10.1007/s004530079058x}, volume = {50}, year = {2008}, }