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 dist ance 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 not equal 3, the case t = 3 still remains open. In this art icle, we show that each directed path graph G has a tree 3-spanner T by mea ns of a linear-time algorithm constructing T. Moreover, the output tree 3-s panner 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. (C) 1999 John Wiley & Sons, Inc.