Title | ||
---|---|---|
A linear time algorithm for constructing tree 3-spanner in simple chordal bipartite graphs |
Abstract | ||
---|---|---|
A spanning tree T of a graph G is called 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. Given a graph G and an integer t, the tree t-spanner problem asks whether G admits a tree t-spanner. It is known that the tree t-spanner problem is NP-complete for chordal bipartite graphs for t ges 5 whereas the complexity status of the cases t = 3 and t = 4 are open. In this paper, we study the tree 3- spanner problem in simple chordal bipartite graphs which is a subclass of chordal bipartite graphs. We have shown that this class need not admit tree 3-spanner in general. First, we present a structural characterization of tree 3- spanner admissible simple chordal bipartite graphs. Based on this characterization, we propose a linear time algorithm to recognize tree 3-spanner admissible simple chordal bipartite graphs. Finally, we present a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible simple chordal bipartite graph. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1109/ICIT.2006.12 | Bhubaneswar |
Keywords | Field | DocType |
tree t-spanner,linear time algorithm,bipartite graph,admissible simple chordal bipartite,tree tspanner,graph g,simple chordal bipartite graph,chordal bipartite graph,tree t-spanner admissible graph,tree t-spanner problem,tree 3-spanner,spanning tree,computational complexity,np complete problem | Trémaux tree,Tree-depth,Computer science,K-ary tree,Chordal bipartite graph,Chordal graph,Tree decomposition,Algorithm,Spanning tree,Gomory–Hu tree | Conference |
ISBN | Citations | PageRank |
0-7695-2635-7 | 0 | 0.34 |
References | Authors | |
10 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Anita Das | 1 | 0 | 0.34 |
B. S. Panda | 2 | 99 | 21.18 |
Rajendra P. Lal | 3 | 0 | 0.34 |