Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem
Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem
复制标题
最大权内部生成树问题的近似算法
DOI：
10.1007/s00453-018-00533-w
复制
发表时间：
2016-08
期刊：
影响因子：
1.1
通讯作者：
Wang Dan
中科院分区：
文献类型：
--
作者：
Chen Zhi-Zhong;Lin Guohui;Wang Lusheng;Chen Yong;Wang Dan
给定一个顶点加权的连通图，最大权值内部生成树（简称MwIST）问题要求生成树tof使内部顶点的总权值最大化。未加权的变体，表示为MIST，是NP-hard和APX-hard，目前最好的近似算法已被证明具有13 / 17的性能比。目前最好的MwIST近似算法的性能比为。在本文中，我们提出了一种基于MwIST和最大权值匹配之间的新关系的简单算法，并表明它达到了明显更好的近似比1/2。对于无爪图，我们设计了一个7/12近似算法。
Given a vertex-weighted connected graph, the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning treeTofGsuch that the total weight of internal vertices inTis maximized. The unweighted variant, denoted as MIST, is NP-hard and APX-hard, and the currently best approximation algorithm has a proven performance ratio of 13 / 17. The currently best approximation algorithm for MwIST only has a performance ratio of, for any. In this paper, we present a simple algorithm based on a novel relationship between MwIST and maximum weight matching, and show that it achieves a significantly better approximation ratio of 1/2. When restricted to claw-free graphs, a special case previously studied, we design a 7/12-approximation algorithm.
登录
查看更多内容
DOI：
10.1007/978-3-319-21840-3_41
发表时间：
2014-12
期刊：
ArXiv
影响因子：
--
作者：
Wenjun Li;Jian-xin Wang;Jianer Chen;Yixin Cao
通讯作者：
Wenjun Li;Jian-xin Wang;Jianer Chen;Yixin Cao
影响因子：
1
作者：
Zhi-Zhong Chen;Youta Harada;Fei Guo;Lusheng Wang
通讯作者：
Lusheng Wang
DOI：
--
发表时间：
2010
期刊：
--
影响因子：
--
作者：
Gábor Salamon
通讯作者：
Gábor Salamon
DOI：
10.1007/978-3-319-13075-0_37
发表时间：
2014-12
期刊：
--
影响因子：
--
作者：
Xingfu Li;Daming Zhu
通讯作者：
Xingfu Li;Daming Zhu
影响因子：
1.1
作者：
Martin Knauer;J. Spoerhase
通讯作者：
Martin Knauer;J. Spoerhase