A 2k-vertex Kernel for Maximum Internal Spanning Tree
A 2k-vertex Kernel for Maximum Internal Spanning Tree
复制标题
DOI：
10.1007/978-3-319-21840-3_41
复制
发表时间：
2014-12
期刊：
影响因子：
--
通讯作者：
Wenjun Li;Jian-xin Wang;Jianer Chen;Yixin Cao
中科院分区：
文献类型：
--
作者：
Wenjun Li;Jian-xin Wang;Jianer Chen;Yixin Cao
我们考虑最大内部生成树问题的参数化版本：给定一个ann-顶点图和一个参数k，这个图是否有一个至少有k个内部顶点的生成树？Fomin等人[J. Comput.系统科学，79：1-6]精心制作了一个非常巧妙的约简规则，并表明简单地应用这个规则就足以为这个问题产生一个3 k-顶点核。在这里，我们提出了一种新的方法来使用相同的约简规则，从而改进了2k-顶点核。我们的算法适用于第一个贪婪的过程，包括一系列的本地交换操作，结束与本地最优的生成树，然后使用这个特殊的树，找到一个可简化的结构。作为我们的核的推论，我们得到了一个时间确定性算法，改进了以前的所有算法。
We consider the parameterized version of the maximum internal spanning tree problem: given ann-vertex graph and a parameterk, does the graph have a spanning tree with at leastkinternal vertices? Fomin et al. [J. Comput. System Sci., 79:1–6] crafted a very ingenious reduction rule, and showed that a simple application of this rule is sufficient to yield a 3k-vertex kernel for this problem. Here we propose a novel way to use the same reduction rule, resulting in an improved 2k-vertex kernel. Our algorithm applies first a greedy procedure consisting of a sequence of local exchange operations, which ends with a local-optimal spanning tree, and then uses this special tree to find a reducible structure. As a corollary of our kernel, we obtain a-time deterministic algorithm, improving all previous algorithms for the problem.