Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem
复制标题
DOI：
10.1007/s00453-013-9827-7
复制
发表时间：
2013-08
期刊：
影响因子：
1.1
通讯作者：
Martin Knauer;J. Spoerhase
中科院分区：
文献类型：
--
作者：
Martin Knauer;J. Spoerhase
我们研究确定给定图的生成树以使内部节点数最大的问题。迄今为止，针对此问题已知的最佳近似算法是 Prieto 和 Sloper，其比率为 2。对于没有下垂节点的图，Salamon 通过本地搜索降低了该系数。然而，他的算法在一般图上的近似行为仍然是开放的。在本文中，我们展示了萨拉蒙算法的简化且更快的版本，即使在一般图上也能产生 a 近似。除此之外，我们还研究了问题的节点加权变体，Salamon 实现了 2⋅Δ(G)−3 的比率。扩展 Salamon 的方法，对于任何 ϵ>0，我们得到一个因子 3+ϵ。我们用最坏的情况实例来补充我们的结果，表明我们的分析是严格的。
We examine the problem of determining a spanning tree of a given graph such that the number of internal nodes is maximum. The best approximation algorithm known so far for this problem is due to Prieto and Sloper and has a ratio of 2. For graphs without pendant nodes, Salamon has lowered this factor toby means of local search. However, the approximative behaviour of his algorithm on general graphs has remained open. In this paper we show that a simplified and faster version of Salamon’s algorithm yields a-approximation even on general graphs. In addition to this, we investigate a node weighted variant of the problem for which Salamon achieved a ratio of 2⋅Δ(G)−3. Extending Salamon’s approach we obtain a factor of 3+ϵfor anyϵ>0. We complement our results with worst case instances showing that our analyses are tight.