Maxstretch reduction for tree spanners
(2005) 9th International Workshop, WADS 2005 In Algorithms and Data Structures / Lecture Notes in Computer Science 3608. p.122133 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... (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 NPhard 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/220496
 author
 Iwama, K; Lingas, Andrzej ^{LU} and Okita, M
 organization
 publishing date
 2005
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 Algorithms and Data Structures / Lecture Notes in Computer Science
 volume
 3608
 pages
 122  133
 publisher
 Springer
 conference name
 9th International Workshop, WADS 2005
 external identifiers

 wos:000231873500012
 scopus:26844486244
 ISSN
 16113349
 03029743
 ISBN
 9783540281016
 DOI
 10.1007/11534273
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 9057d95e64b84fb988c975809aadded9 (old id 220496)
 date added to LUP
 20070817 16:58:50
 date last changed
 20170101 04:52:13
@inproceedings{9057d95e64b84fb988c975809aadded9, 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 NPhard 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, K and Lingas, Andrzej and Okita, M}, booktitle = {Algorithms and Data Structures / Lecture Notes in Computer Science}, isbn = {9783540281016}, issn = {16113349}, language = {eng}, pages = {122133}, publisher = {Springer}, title = {Maxstretch reduction for tree spanners}, url = {http://dx.doi.org/10.1007/11534273}, volume = {3608}, year = {2005}, }