Tree spanners on chordal graphs: complexity and algorithms
Tree spanners on chordal graphs: complexity and algorithms
复制标题
弦图上的树扳手：复杂性和算法
DOI：
10.1016/s0304-3975(03)00424-9
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
V. B. Le
中科院分区：
文献类型：
--
作者：
A. Brandstädt;F. Dragan;Hoàng;V. B. Le
图G中的树生成树T是G的一棵生成树，使得每对顶点在T中的距离至多是它们在G中的距离的t倍。TREEt-SPAN NER问题问的是给定t，一个图是否允许一棵树t-SPAN。我们充分加强了Cai和Corneil（SIAM J. Discrete Math.8（1995）359-387）的硬度结果，证明了对于任意t ≥ 4，TREEt-SPAN在直径至多为t+1（如果t是偶数）和至多为t+2（如果t是奇数）的弦图上分别是NP-完全偶数的。然后我们指出，每一个直径至多为t−1（分别为t−2）的弦图，只要t <$2是偶数（分别为t <$3是奇数），就有一棵树t-t <$1，并且这样的树t-t <$1可以在线性时间内构造。树3-SPAN的复杂性状态仍然是开放的弦图，即使在子类的无向路径图，是强弦。对于弦图的其他重要子类，如非常强弦图（包含所有区间图）、1-分裂图（包含所有分裂图）和直径不超过2的弦图，我们能够有效地判定树3-SPAN。
A treet-spannerT in a graph G is a spanning tree of G such that the distance in T between every pair of vertices is at most t times their distance in G. The TREEt-SPANNER problem asks whether a graph admits a tree t-spanner, given t. We substantially strengthen the hardness result of Cai and Corneil (SIAM J. Discrete Math. 8 (1995) 359–387) by showing that, for any t⩾4, TREEt-SPANNER is NP-complete even on chordal graphs of diameter at most t+1 (if t is even), respectively, at most t+2 (if t is odd). Then we point out that every chordal graph of diameter at most t−1 (respectively, t−2) admits a tree t-spanner whenever t⩾2 is even (respectively, t⩾3 is odd), and such a tree spanner can be constructed in linear time. The complexity status of TREE 3-SPANNER still remains open for chordal graphs, even on the subclass of undirected path graphs that are strongly chordal as well. For other important subclasses of chordal graphs, such as very strongly chordal graphs (containing all interval graphs), 1-split graphs (containing all split graphs) and chordal graphs of diameter at most 2, we are able to decide TREE 3-SPANNER efficiently.