| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | 低度图的点覆盖和独立集问题下界改进 |
| 作者 | 肖鸣宇1) 陈建二2),3) 韩旭里1) |
| 作者单位 | 1)(中南大学数学科学与计算技术学院 长沙 410083) 2)(中南大学信息科学与工程学院 长沙 410083) 3)(德克萨斯A&M大学计算机科学学院 德克萨斯州77843-3112 美国) |
| 发表年份 | 2005 |
| 发表月份 | 2期(153—160) |
| 文章摘要 | 摘要 给出了一种提高低度图点覆盖和独立集问题下界的精确算法.通过分析如何有效地减少图中的顶点来打破原问题的NP-Hard结构建立起搜索递推关系；得出3度图的最小点覆盖问题的解决时间为O(11033n)，参数化的3度图点覆盖问题的解决时间为O(kn+12174k)；将此算法应用到3度图的最大独立集问题上，可以得到运行时间为O(11033n)的解.以上3结果均打破原有最佳下界. 关键词 点覆盖;独立集;精确算法;参数计算 中图法分类号 TP301 |