Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421090 | Discrete Applied Mathematics | 2015 | 6 Pages |
A tree tt-spanner of an unweighted graph GG is a spanning tree TT such that for every two vertices their distance in TT is at most tt times their distance in GG. Given an unweighted graph GG and a positive integer tt as input, the Treett-spanner problem is to compute a tree tt-spanner of GG if one exists. This decision problem is known to be NP-complete even in the restricted class of unweighted planar graphs. We present a linear-time reduction from Treett-spanner in outerplanar graphs to the supply–demand tree partition problem. Based on this reduction, we obtain a linear-time algorithm to solve Treett-spanner in outerplanar graphs. Consequently, we show that the minimum value of tt for which an input outerplanar graph on nn vertices has a tree tt-spanner can be found in O(nlogn)O(nlogn) time.