摘要
给出了一种提高低度图点覆盖和独立集问题下界的精确算法.通过分析如何有效地减少图中的顶点来打破原问题的NP Hard结构建立起搜索递推关系;得出3度图的最小点覆盖问题的解决时间为 O(1 1033n),参数化的3度图点覆盖问题的解决时间为O(kn+1 2174k);将此算法应用到 3 度图的最大独立集问题上,可以得到运行时间为O(1 1033n)的解.以上3结果均打破原有最佳下界.
An exact algorithm to improve the upper bound of vertex cover and independent set problem for low-degree graphs is presented. The algorithm constructs recurrence relations by concentrating on how many vertices be reduced then the NP-hard structure of the problem is broken. With this idea, running time O(l.1033n) for minimum vertex cover problem on degree-3 graphs is proved. For parameterized vertex cover problem on degree-3 graphs, it also can be solved with running time O(kn+1.2174k). Using the algorithm to the maximum independent set problem on degree-3 graphs, the authors can get the running time O(l.1033n). All of the above results improve the previous best results.
出处
《计算机学报》
EI
CSCD
北大核心
2005年第2期153-160,共8页
Chinese Journal of Computers
