| 最多叶子生成树问题的核化算法 |
| |
| 引用本文： | 高文宇.最多叶子生成树问题的核化算法[J].计算机学报,2010,33(12). |
| |
| 作者姓名： | 高文宇 |
| |
| 作者单位： | 广东商学院信息学院; |
| |
| 摘 要： | 对算法领域的最多叶子生成树问题进行了深入研究,提出了对简单连通图2度节点的化简规则,并证明了不含2度节点的图的生成树的叶子节点数的下限为(N+6)/4,给出了构造这样一棵生成树的构造性方法.基于上述化简规则和所证明的结论,给出了最多叶子生成树问题的核化算法,该核化算法可以在O(n2)时间内得到一个4k-6大小的线性核.对于这样一个较小的核,将大大提高相关的参数算法和近似算法的性能.
|
| 关 键 词： | 最多叶子生成树 核化 参数算法 |
Kernelization Algorithm of Maximum Leaf Spanning Tree |
| |
| GAO Wen-Yu.Kernelization Algorithm of Maximum Leaf Spanning Tree[J].Chinese Journal of Computers,2010,33(12). |
| |
| Authors: | GAO Wen-Yu |
| |
| Affiliation: | GAO Wen-Yu(School of Computer Science,Guangdong University of Business Studies,Guangzhou 510320) |
| |
| Abstract: | This paper proposes 2-degree node reduction rules for Maximum Leaf Spanning Tree problem,and proves that any connected graph without 2-degree node has a spanning tree including at least(N+6)/4 leafs.The reduction rules and the low bound are used to construct a kernelization algorithm for Maximum Leaf Spanning Tree problem,which algorithm can output a 4k-6 linear kernel of Maximum Leaf Spanning Tree problem in O(n2)time. |
| |
| Keywords: | maximum leaf spanning tree kernelization parameterized algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
