Optimal tree 3-spanners in directed path graphs

✍ Scribed by Le, Ho�ng-Oanh; Le, Van Bang

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 122 KB
• Volume: 34
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199909)34:2<81::aid-net1>3.0.co;2-p

✦ Synopsis

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.