loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
9th International Conference on Information Technology (ICIT'06)
A linear time algorithm for constructing tree 3-spanner in simple chordal bipartite graphs
Bhubaneswar, India
December 18-December 21
ISBN: 0-7695-2635-7
Anita Das, Indian Institute of Technology Delhi
B.S. Panda, Indian Institute of Technology Delhi
Rajendra P. Lal, Indian Institute of Technology Delhi
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 tspanner 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 /ge 5 whereas the complexity status of the cases t = 3and t = 4are 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.
Citation:
Anita Das, B.S. Panda, Rajendra P. Lal, "A linear time algorithm for constructing tree 3-spanner in simple chordal bipartite graphs," icit, pp.301-304, 9th International Conference on Information Technology (ICIT'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.