顶点覆盖问题线性内核算法

• 作者: Rudolf Fleischer 朱洪 蔡晟
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 参数复杂性 内核化 线性内核 定点覆盖
• 年，卷（期）: 2008,（z1）
• 所属期刊栏目: 算法:设计与分析
• 页码范围: 53-56
• 页数: 4页
• 分类号: TP301.6
• 字数: 3916字
• 语种: 中文

摘要

参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先通过顶点覆盖问题的2近似算法,将图的顶点集合分成两个顶点集合A,B,进而通过一系列规约将原始图的顶点覆盖问题转换到新图的顶点覆盖问题,然后证明了新图的顶点数目至多为2k,并且2k是这个问题的下界(k为参数具体定义见文章).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	蔡晟	复旦大学信息工程学院计算机系	3	12	2.0	3.0
2	Rudolf Fleischer	复旦大学信息工程学院计算机系	4	4	1.0	2.0
3	朱洪	华东师范大学软件学院	2	5	1.0	2.0