Deeper Local Search for Better Approximation on Maximum Internal Spanning Trees
Deeper Local Search for Better Approximation on Maximum Internal Spanning Trees
复制标题
DOI：
10.1007/978-3-662-44777-2_53
复制
发表时间：
2014-09
期刊：
影响因子：
--
通讯作者：
Wenjun Li;Jianer Chen;Jian-xin Wang
中科院分区：
文献类型：
--
作者：
Wenjun Li;Jianer Chen;Jian-xin Wang
生成树一直是图算法研究的基础。本文研究了图的生成树内部结点个数最大的优化问题MaxIST，它是著名的哈密顿路径问题的推广。提出了一种基于深度局部搜索策略的多项式时间逼近算法，给出了支持对这种深度局部搜索策略产生的生成树进行深入分析的组合结构，并证明了该算法对MaxIST问题的逼近比为1.5，改进了以往的5/3的最佳逼近算法。
Spanning tree has been fundamental in the research of graph algorithms. In this paper, we study the optimization problemMaxIST, which maximizes the number of internal nodes in a spanning tree of a given graph, and is a generalization of the famousHamiltonian-Pathproblem. We present a polynomial-time approximation algorithm based on a deep local search strategy, identify combinatorial structures that support thorough analysis on the spanning trees resulted from such deep local search strategies, and prove that our algorithm has an approximation ratio 1.5 for theMaxISTproblem, improving the previous best approximation algorithm of ratio 5/3 for the problem.