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 b log vertical bar V(G)vertical bar are examined. (C) 2017 Elsevier B.V. All rights reserved.