最小顶点覆盖问题的加权分治算法  

Measure and Conquer Approach for the Minimum Vertex Cover Problem

作　　者：陈吉珍 宁爱兵[1] 支志兵 王永斐 张惠珍[1] 

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《运筹与管理》2015年第5期151-155,共5页Operations Research and Management Science

基　　金：国家自然科学基金(71401106);上海市一流学科建设项目资助(S1201YLXK);高等学校博士学科点专项科研基金联合资助课题(20123120120005)

摘　　要：最小顶点覆盖问题是组合优化中经典NP—Hard问题之一，其在实际问题中有着广泛的应用。加权分治技术是算法设计和复杂性分析中的新技术，该技术主要用于对分支降阶的递归算法进行复杂性分析，其核心思想可以理解为依据问题不同的特征设置一组相应的权值，以求降低该算法最坏情况下的时间复杂度。本文依据加权分治技术设计出一个分支降阶递归算法来求解最小顶点覆盖问题，并通过加权分治技术分析得出该算法的时间复杂度为O（1．255n），优于常规分析下的时间复杂度O（1．325n）。本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的。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 cations in the analysis of exact algorithms. can significantly speed up exact algorithms and has wide appli-cations in the analysis of exact algorithms.

关 键 词：图论 算法复杂性 加权分治技术 分支降阶技术 最小顶点覆盖 

分 类 号：O223[理学—运筹学与控制论]