最多叶子生成树问题的核化算法

• 作者: 高文宇
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 最多叶子生成树 核化 参数算法
• 年，卷（期）: 2010,（12）
• 页码范围: 2211-2218
• 分类号: TP301
• 字数: 7563字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2010.02211

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	高文宇	广东商学院信息学院	19	173	7.0	12.0