期刊文献+

最小顶点覆盖问题的加权分治算法 被引量:5

Measure and Conquer Approach for the Minimum Vertex Cover Problem
下载PDF
导出
摘要 最小顶点覆盖问题是组合优化中经典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.
出处 《运筹与管理》 CSSCI CSCD 北大核心 2015年第5期151-155,共5页 Operations Research and Management Science
基金 国家自然科学基金(71401106) 上海市一流学科建设项目资助(S1201YLXK) 高等学校博士学科点专项科研基金联合资助课题(20123120120005)
关键词 图论 算法复杂性 加权分治技术 分支降阶技术 最小顶点覆盖 graph theory algorithm complexity Measure and Conquer Bbranch and Reduce Minimum Vertex covey
  • 相关文献

参考文献1

二级参考文献7

  • 1杨杰.改进的最优顶点覆盖贪心边近似算法[J].计算机应用,2006,26(1):149-151. 被引量:6
  • 2Chen J, Kanj I, Jia W. Vertex cover: further observations and further improvements [J]. Journal of Algorithms, 2001,41 (2) : 280-301.
  • 3Balasubramanian R, Fellows M R, Raman V. An improved fixed parameter algorithm for vertex cover [J].Information Processing Letters, 1998, 65(3):163-168.
  • 4Garey M R, Johnson D S. Strong NP-completeness results, motiration, examples, and implications [J]. Journal of ACM, 1978, 25(3): 499-508.
  • 5Wang Xiao-dong. Some special cases of NP-complete problems[J].Journal of Fuzhou University, 1999,27(5):10-13.
  • 6He Feng, Che Wen-gang. An efficient algorithm for constraint bipartite vertexcover[J]. Journal of Kunming University of Science and Technology (Science and Technology), 2003, 28(5):85-89.
  • 7Yao Zhao-zhuo. Design and analysis of vertex covered problem by greedy algorithm[J].Journal of Fuzhou University, 2001, 29(1):8-11.

共引文献8

同被引文献30

引证文献5

二级引证文献5

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部