Tree spanners of bounded degree graphs

A tree t-spanner of a graph G is a spanning tree of G such that the distance between pairs of vertices in the tree is at most t times their distance in G. Deciding tree t-spanner admissible graphs has been proved to be tractable for t<3 and NP-complete for t>3, while the complexity status of this problem is unresolved when t=3. For every t>2 and b>0, an efficient dynamic programming algorithm to decide tree t-spanner admissibility of graphs with vertex degrees less than b is presented. Only for t=3, the algorithm remains efficient, when graphs G with degrees less than blog|V(G)| are examined.