An approximation algorithm for maximum internal spanning tree
An approximation algorithm for maximum internal spanning tree
复制标题
一种最大内生成树的近似算法
DOI：
10.1007/s10878-017-0245-7
复制
发表时间：
2016-07
影响因子：
1
通讯作者：
Lusheng Wang
中科院分区：
文献类型：
--
作者：
Zhi-Zhong Chen;Youta Harada;Fei Guo;Lusheng Wang
给定一个图G，最大内部生成树问题(简称MIST)要求计算一棵生成树TOFG，使得图G中的内部顶点数最大化。MIST在设计经济高效的通信网络和供水网络方面具有潜在的应用价值，因此在文献中得到了广泛的研究。MIST是NP难的，因此在文献中已经设计了许多MIST的多项式时间近似算法。以前最好的雾化多项式时间近似算法达到了。在本文中，我们首先设计了一个更简单的算法，它获得了与以前最好的算法相同的比率和相同的时间复杂度。然后，我们将该算法改进为一种新的近似算法，该算法在相同的时间复杂度下获得了更好的比(即)。我们的新算法比以前的最好算法探索了问题的更深层次的结构。所发现的结构可能被用来为将来的问题设计更好的近似或参数化算法。
Given a graphG, themaximum internal spanning tree problem(MIST for short) asks for computing a spanning treeTofGsuch that the number of internal vertices inTis maximized. MIST has possible applications in the design of cost-efficient communication networks and water supply networks and hence has been extensively studied in the literature. MIST is NP-hard and hence a number of polynomial-time approximation algorithms have been designed for MIST in the literature. The previously best polynomial-time approximation algorithm for MIST achieves a ratio of. In this paper, we first design a simpler algorithm that achieves the same ratio and the same time complexity as the previous best. We then refine the algorithm into a new approximation algorithm that achieves a better ratio (namely,) with the same time complexity. Our new algorithm explores much deeper structure of the problem than the previous best. The discovered structure may be used to design even better approximation or parameterized algorithms for the problem in the future.
登录
查看更多内容
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
DOI：
10.1016/j.jcss.2015.11.008
发表时间：
2014-02
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
H. Shachnai;M. Zehavi
通讯作者：
H. Shachnai;M. Zehavi
DOI：
--
发表时间：
2010
期刊：
--
影响因子：
--
作者：
Gábor Salamon
通讯作者：
Gábor Salamon
DOI：
--
发表时间：
2014-09
期刊：
ArXiv
影响因子：
--
作者：
Xingfu Li;Daming Zhu
通讯作者：
Xingfu Li;Daming Zhu
DOI：
10.1007/978-3-319-13075-0_37
发表时间：
2014-12
期刊：
--
影响因子：
--
作者：
Xingfu Li;Daming Zhu
通讯作者：
Xingfu Li;Daming Zhu