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

摘要

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