Paper Info
Title
Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction
Abstract
A spanning tree T of a graph G is called a treet-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 treet-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t=4, and is linearly solvable for t=1 and t=2. The case t=3 still remains open. A directed path graph is called a 2-sep directed path graph if all of its minimal a-b vertex separator for every pair of non-adjacent vertices a and b are of size two. Le and Le [H.-O. Le, V.B. Le, Optimal tree 3-spanners in directed path graphs, Networks 34 (2) (1999) 81-87] showed that directed path graphs admit tree 3-spanners. However, this result has been shown to be incorrect by Panda and Das [B.S. Panda, Anita Das, On tree 3-spanners in directed path graphs, Networks 50 (3) (2007) 203-210]. In fact, this paper observes that even the class of 2-sep directed path graphs, which is a proper subclass of directed path graphs, need not admit tree 3-spanners in general. It, then, presents a structural characterization of tree 3-spanner admissible 2-sep directed path graphs. Based on this characterization, a linear time recognition algorithm for tree 3-spanner admissible 2-sep directed path graphs is presented. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep directed path graph is proposed.
Year
DOI
Venue
2009
10.1016/j.dam.2008.06.026
Discrete Applied Mathematics
Keywords
Field
DocType
tree t-spanner,treet-spanner admissible graph,anita das,tree spanner,graph algorithms,tree 3-spanner,linear time algorithm,directed path graphs,tree 3-spanners,distance in graphs,graph g,optimal tree,b.s. panda,path graph,spanning tree,linear time
Block graph,Discrete mathematics,Combinatorics,Tree-depth,Path (graph theory),Tree (graph theory),K-ary tree,Pathwidth,Longest path problem,Widest path problem,Mathematics
Journal
Volume
Issue
ISSN
157
9
Discrete Applied Mathematics
Citations 
PageRank 
References 
2
0.39
13
Authors
2
Name
Order
Citations
PageRank
B. S. Panda19921.18
Anita Das220.39