An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs

作者：Dragan Feodor F^*; Koehler Ekkehard

来源：Algorithmica, 2014, 69(4): 884-905.

DOI：10.1007/s00453-013-9765-4

• Graph algorithms
• Approximation algorithms
• Tree t-spanner problem
• Minimum max-stretch spanning tree problem
• Generalized chordal graphs
• Robertson-Seymour's tree-decomposition
• Balanced separators

A spanning tree T of a graph G is called a tree t-spanner of G if the distance between every pair of vertices in T is at most t times their distance in G. In this paper, we present an algorithm which constructs for an n-vertex m-edge unweighted graph G:
-a tree (2[log(2)n])-spanner in O(mlogn) time, if G is a chordal graph (i.e., every induced cycle of G has length 3);
-a tree (2 rho[log(2)n)-spanner in O(mnlog2 n) time or a tree (12 rho[log(2)n)-spanner in O(mlog n) time, if G is a graph admitting a Robertson- Seymour's tree-decomposition with bags of radius at most. in G; and
-a tree (2[t/2][log(2)n)-spanner in O(mnlog(2)n) time or a tree (6t[log2n])spanner in O(mlog n) time, if G is an arbitrary graph admitting a tree t-spanner.
For the latter result we use a new necessary condition for a graph to have a tree t-spanner: if a graph G has a tree t-spanner, then G admits a Robertson-Seymour's tree-decomposition with bags of radius at most [t/2] and diameter at most t in G.

• 出版日期2014-8