低度图的点覆盖和独立集问题下界改进

• 作者: 肖鸣宇 陈建二 韩旭里
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 点覆盖 独立集 精确算法 参数计算
• 年，卷（期）: 2005,（2）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 153-160
• 页数: 8页
• 分类号: TP301
• 字数: 7815字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2005.02.002

摘要

给出了一种提高低度图点覆盖和独立集问题下界的精确算法.通过分析如何有效地减少图中的顶点来打破原问题的NP-Hard结构建立起搜索递推关系;得出3度图的最小点覆盖问题的解决时间为O(1.1033n),参数化的3度图点覆盖问题的解决时间为O(kn+1.2174k);将此算法应用到3度图的最大独立集问题上,可以得到运行时间为O(1.1033n)的解.以上3结果均打破原有最佳下界.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	韩旭里	中南大学数学科学与计算技术学院	119	1266	16.0	32.0
2	肖鸣宇	中南大学数学科学与计算技术学院	8	39	4.0	6.0