A 4/3-approximation algorithm for finding a spanning tree to maximize its internal vertices
A 4/3-approximation algorithm for finding a spanning tree to maximize its internal vertices
复制标题
DOI：
--
复制
发表时间：
2014-09
期刊：
影响因子：
--
通讯作者：
Xingfu Li;Daming Zhu
中科院分区：
文献类型：
--
作者：
Xingfu Li;Daming Zhu
本文的重点是寻找一个图的生成树，以最大化其内部顶点的数量。我们提出了一种近似算法，可以在无向简单图上实现性能比$\frac{4}{3}$。这改进了之前最著名的性能比为$\frac{5}{3}$的近似算法。我们的算法得益于对生成树内部顶点数量边界的新观察，该观察揭示了无向简单图的生成树的内部顶点数量少于该图的最大路径循环覆盖的边缘数量。我们还可以给出一个例子来证明，对于这个算法来说，性能比$\frac{4}{3}$实际上是紧的。为了确定近似这个问题的困难程度，我们证明了找到一个无向简单图的生成树来最大化其内部顶点是Max-SNP-Hard。
This paper focuses on finding a spanning tree of a graph to maximize the number of its internal vertices. We present an approximation algorithm for this problem which can achieve a performance ratio $\frac{4}{3}$ on undirected simple graphs. This improves upon the best known approximation algorithm with performance ratio $\frac{5}{3}$ before. Our algorithm benefits from a new observation for bounding the number of internal vertices of a spanning tree, which reveals that a spanning tree of an undirected simple graph has less internal vertices than the edges a maximum path-cycle cover of that graph has. We can also give an example to show that the performance ratio $\frac{4}{3}$ is actually tight for this algorithm. To decide how difficult it is for this problem to be approximated, we show that finding a spanning tree of an undirected simple graph to maximize its internal vertices is Max-SNP-Hard.