作　　者： ;

机构地区： 广东商学院信息学院

出　　处： 《计算机学报》 2010年第12期2211-2218,共8页

摘　　要： 对算法领域的最多叶子生成树问题进行了深入研究,提出了对简单连通图2度节点的化简规则,并证明了不含2度节点的图的生成树的叶子节点数的下限为(N+6)/4,给出了构造这样一棵生成树的构造性方法.基于上述化简规则和所证明的结论,给出了最多叶子生成树问题的核化算法,该核化算法可以在O(n2)时间内得到一个4k-6大小的线性核.对于这样一个较小的核,将大大提高相关的参数算法和近似算法的性能. 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.

关 键 词： 最多叶子生成树 核化 参数算法

领　　域： [自动化与计算机技术] [自动化与计算机技术]