Optimal Tree 3-Spanners in Directed Path Graphs

In a graph G, a spanning tree T is called a tree t-spanner of G if the distance between any two vertices in T is at most t times their distance in G. While the complexity of finding a tree t-spanner of a given graph is known for any fixed t <> 3, the case t = 3 still remains open. In this article, we show that each directed path graph G has a tree 3-spanner T by means of a linear-time algorithm constructing T. Moreover, the output tree 3-spanner T is optimal in the sense that G has a tree 2-spanner if and only if T is a tree 2-spanner of G. © 1999 John Wiley & Sons, Inc. Networks 34: 81-87, 1999