未找到相关数据
低度图的点覆盖和独立集问题下界改进
被引：11
作者：
肖鸣宇
陈建二
韩旭里
机构：
[1] 中南大学数学科学与计算技术学院,中南大学信息科学与工程学院,中南大学数学科学与计算技术学院长沙,长沙德克萨斯A&M大学计算机科学学院德克萨斯州美国,长沙
来源：
关键词：
点覆盖;
独立集;
精确算法;
参数计算;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
给出了一种提高低度图点覆盖和独立集问题下界的精确算法.通过分析如何有效地减少图中的顶点来打破原问题的NP Hard结构建立起搜索递推关系;得出3度图的最小点覆盖问题的解决时间为 O(1 1033n),参数化的3度图点覆盖问题的解决时间为O(kn+1 2174k);将此算法应用到 3 度图的最大独立集问题上,可以得到运行时间为O(1 1033n)的解.以上3结果均打破原有最佳下界.
引用
收藏
页码：153 / 160
页数：8
相关论文