《计算机学报》文章摘要   全文下载
文章题目	最多叶子生成树问题的核化算法
作者	高文宇
作者单位	(广东商学院信息学院 广州 510320)
发表年份	2010
发表月份	12期(2211—2218)
文章摘要	摘要 对算法领域的最多叶子生成树问题进行了深入研究，提出了对简单连通图2度节点的化简规则，并证明了不含2度节点的图的生成树的叶子节点数的下限为(N+6)/4，给出了构造这样一棵生成树的构造性方法.基于上述化简规则和所证明的结论，给出了最多叶子生成树问题的核化算法，该核化算法可以在O(n2)时间内得到一个4k-6大小的线性核.对于这样一个较小的核，将大大提高相关的参数算法和近似算法的性能. 关键词 最多叶子生成树；核化；参数算法 中图法分类号 TP301 DOI号: 10.3724/SP.J.1016.2010.02211