Approximating Spanning Trees with Few Branches
Approximating Spanning Trees with Few Branches
复制标题
DOI：
10.1007/s00224-014-9556-6
复制
发表时间：
2012-09
影响因子：
0.5
通讯作者：
Markus Chimani;J. Spoerhase
中科院分区：
文献类型：
--
作者：
Markus Chimani;J. Spoerhase
给定一个无向连通图，最小分支节点生成树问题的目标是找到一个最小节点数大于2度的生成树。这个问题是由网络设计问题引起的，其中连接比简单的端节点或贯穿节点要昂贵得多，因此应该避免。不幸的是，很难识别承认客观值为零的实例，这使得寻找有保证的近似比率是徒劳的。我们建议研究一个补充的公式，称为最大路径节点生成树，其目标是找到一个生成树，使节点的数量最大化，其度最多为2。虽然两种公式的最优解（和实际应用）是一致的，但我们的公式被证明更适合于近似。事实上，它允许一个平凡的1/2近似算法。我们的主要贡献是一个局部搜索算法，它保证了6/11的比例，并表明问题是apx困难的，也就是说，它不允许PTAS。
Given an undirected, connected graph, the aim of theminimum branch-node spanning treeproblem is to find a spanning tree with the minimum number of nodes of degree larger than 2. The problem is motivated by network design problems where junctions are significantly more expensive than simple end- or through-nodes, and are thus to be avoided. Unfortunately, it is NP-hard to recognize instances that admit an objective value of zero, rendering the search for guaranteed approximation ratios futile.We suggest to investigate acomplementaryformulation, calledmaximum path-node spanning tree, where the goal is to find a spanning tree that maximizes the number of nodes with degree at most two. While the optimal solutions (and the practical applications) of both formulations coincide, our formulation proves more suitable for approximation. In fact, it admits a trivial 1/2-approximation algorithm. Our main contribution is a local search algorithm that guarantees a ratio of 6/11, as well as showing that the problem is APX-hard, i.e., it does not allow a PTAS.