کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420230 | 683910 | 2010 | 23 صفحه PDF | دانلود رایگان |
A spanning tree TT of a graph GG is said to be a tree tt-spanner if the distance between any two vertices in TT is at most tt times their distance in GG. A graph that has a tree tt-spanner is called a tree tt-spanner admissible graph . The problem of deciding whether a graph is tree tt-spanner admissible is NP-complete for any fixed t≥4t≥4 and is linearly solvable for t≤2t≤2. The case t=3t=3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a−ba−b vertex separators for every pair of non-adjacent vertices aa and bb are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners. This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed.
Journal: Discrete Applied Mathematics - Volume 158, Issue 17, 28 October 2010, Pages 1913–1935