Name
Abstract | ||
|---|---|---|
A spanning tree T of a graph G is said to be a tree t-spanner if the distance between any two vertices in T is at most t times their distance in G. While the complexity of the problem of recognizing whether a graph has a tree t-spanner is known for any fixed t≠3, the case t = 3 is still open. H.-O. Le and V. B. Le (1999, Networks, 34(2), 81-87) have shown that every directed path graph admits a tree 3-spanner by proposing an algorithm to construct a tree 3-spanner of a given directed path graph. In this paper, we point out a flaw in their algorithm by producing a directed path graph for which their algorithm fails to produce a tree 3-spanner although the graph admits a tree 3-spanner. Furthermore, we show that directed path graphs need not admit tree 3-spanners in general. Next, we show that directed path graphs of diameter two always admit tree 2-spanners and hence tree 3-spanners. Finally, we show that a tree 2-spanner of a diameter two directed path graph can be constructed in linear time. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(3), 203–210 2007 |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1002/net.v50:3 | Networks |
Keywords | Field | DocType |
tree t-spanner,wiley periodicals,tree 3-spanners,inc. networks,tree 2-spanner,v. b. le,graph g,tree 2-spanners,path graph,tree 3-spanner,np completeness,spanning trees | Discrete mathematics,Combinatorics,Tree-depth,Tree (graph theory),Tree decomposition,K-ary tree,Spanning tree,Shortest-path tree,Gomory–Hu tree,Mathematics,Widest path problem | Journal |
Volume | Issue | ISSN |
50 | 3 | 0028-3045 |
Citations | PageRank | References |
3 | 0.42 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| B. S. Panda | 1 | 99 | 21.18 |
| Anita Das | 2 | 3 | 0.42 |