计算机工程与应用2016，Vol.52Issue(1)：20-22,109,4.DOI:10.3778/j.issn.1002-8331.1503-0144
图论中最大独立集问题的精确算法
Exact algorithm for maximum independent set problem in graph theory
摘要
Abstract
Independent set problem is a widely studied NP-hard problem in the area of graph theory and has important applications in many fields. Branch and reduce is widely used tool for obtaining exact solutions for NP-hard and NP-complete problem. The main idea of the approach is to solve the problem by fast reducing the size of it, then decomposing it into sub-problems, recursively solving the sub-problems. In order to speed the running time of the algorithm, it adds some rules to reduce the size of the problem. This paper designs an exact algorithm based on branch and reduce to solve maximum independent set problem, and obtains the worst-case time running of the algorithm that is O(1.285n) . The results show that branch and reduce approach can get the exact solution of NP-hard problem in theory.关键词
图论/最小顶点覆盖/快速降阶/精确算法Key words
graph theory/maximum independent set/branch and reduce/exact algorithm分类
数理科学引用本文复制引用
陈吉珍,宁爱兵,支志兵,胡琳琳,张惠珍..图论中最大独立集问题的精确算法[J].计算机工程与应用,2016,52(1):20-22,109,4.基金项目
国家自然科学基金(No.71401106) （No.71401106）
上海市一流学科建设项目(No.S1201YLXK) （No.S1201YLXK）
高等学校博士学科点专项科研基金联合资助课题(No.20123120120005). （No.20123120120005）
