Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms

Abstract: A spanning tree of a graph is said to be a tree -spanner if the distance between any two vertices in is at most times their distance in . A graph that has a tree -spanner is called a tree -spanner admissible graph. The problem of deciding whether a graph is tree -spanner admissible is NP-complete for any fixed and is linearly solvable for . The case still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal vertex separators for every pair of non-adjacent vertices and 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. [ABSTRACT FROM AUTHOR]