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. A graph that has a tree t-spanner is called a tree t-spanner admissible graph. It has been shown in [3] that the problem of recognizing whether a graph admits a tree t-spanner is NP-complete for t ≥ 4. In this paper, we present a linear time algorithm for constructing a tree 4-spanner in a tree 4-spanner admissible 2-tree. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-30561-3_3 | CIT |
Keywords | Field | DocType |
tree t-spanner,linear time algorithm,tree 4-spanner,admissible 2-tree,graph g,tree t-spanner admissible graph,spanning tree | Tree (graph theory),Computer science,K-ary tree,Tree decomposition,Algorithm,Spanning tree,Segment tree,Gomory–Hu tree,Minimum spanning tree,Interval tree | Conference |
Volume | ISSN | ISBN |
3356 | 0302-9743 | 3-540-24126-4 |
Citations | PageRank | References |
1 | 0.36 | 16 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| B. S. Panda | 1 | 99 | 21.18 |
| Anita Das | 2 | 1 | 0.69 |