Approximating the Maximum Internal Spanning Tree Problem via a Maximum Path-Cycle Cover
Approximating the Maximum Internal Spanning Tree Problem via a Maximum Path-Cycle Cover
复制标题
DOI：
10.1007/978-3-319-13075-0_37
复制
发表时间：
2014-12
期刊：
影响因子：
--
通讯作者：
Xingfu Li;Daming Zhu
中科院分区：
文献类型：
--
作者：
Xingfu Li;Daming Zhu
本文主要研究如何在图的内部顶点数最大的情况下寻找一棵生成树。我们给出了生成树内部顶点数的一个新的上界，它表明对于任何无向简单图，任何生成树的内部顶点数都少于最大路圈覆盖的边数。因此，从最大路圈覆盖出发，我们可以在无向简单图上设计出一个具有性能比的近似算法。这改进了Knauer和Spoerhase算法所达到的最佳性能比。此外，我们还可以对算法进行改进，以达到在无叶图上的性能比。
This paper focuses on finding a spanning tree of a graph to maximize its internal vertices in number. We propose a new upper bound for the number of internal vertices in a spanning tree, which shows that for any undirected simple graph, any spanning tree has less internal vertices than the edges a maximum path-cycle cover has. Thus starting with a maximum path-cycle cover, we can devise an approximation algorithm with a performance ratiofor this problem on undirected simple graphs. This improves upon the best known performance ratioachieved by the algorithm of Knauer and Spoerhase. Furthermore, we can improve the algorithm to achieve a performance ratiofor this problem on graphs without leaves.