运筹与管理Issue(5)：151-155,5.
最小顶点覆盖问题的加权分治算法
Measure and Conquer Approach for the Minimum Vertex Cover Problem
摘要
Abstract
Minimum vertex cover set problem is a well-known NP-Hard problem in the area of combinatorial opti-mization and has important applications in many fields.The analytical technology of Measure and Conquer is widely used to analyze the worst-case running time of exact algorithms based on branch and reduce.The main idea of Measure and Conquer is focused on choosing a refined non-standard measure to measure the size of the problem and its sub-problems at the each branching phase.In this work, we first use the technology of Branch and Reduce to design an exact algorithm for the minimum vertex cover problem, then use two kinds of methods to analyze the worst-case time complexity of the algorithm.We improve the worst-case time complexity of the same algorithm from O(1.325n) to O(1.255n) by employing the method of Measure and Conquer.The results of this work indicate that Measure and Conquer approach can significantly speed up exact algorithms and has wide appli-cations in the analysis of exact algorithms.关键词
图论/算法复杂性/加权分治技术/分支降阶技术/最小顶点覆盖Key words
graph theory/algorithm complexity/Measure and Conquer/Bbranch and Reduce/Minimum Vertex cover分类
数理科学引用本文复制引用
陈吉珍,宁爱兵,支志兵,王永斐,张惠珍..最小顶点覆盖问题的加权分治算法[J].运筹与管理,2015,(5):151-155,5.基金项目
国家自然科学基金（71401106）；上海市一流学科建设项目资助（S1201YLXK）；高等学校博士学科点专项科研基金联合资助课题 （）
