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.