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

详细信息    查看全文

• 作者：B.S. P ; a ; Anita Das
• 关键词：Tree spanner ; Distance in graphs ; Graph algorithms ; ; none ; color ; black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-50XTSX0-2&_mathId=mml42&_user=10&_cdi=5629&_pii=S0166218X10002787&_rdoc=8&_issn=016
• 刊名：Discrete Applied Mathematics
• 出版年：2010
• 出版时间：28 October 2010
• 年：2010
• 卷：158
• 期：17
• 页码：1913-1935
• 全文大小：505 K

文摘

A spanning tree T of a graph G is said to be 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. 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≤2. The case t=3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a−b vertex separators for every pair of non-adjacent vertices a and b 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.