期刊文献+

最小顶点覆盖快速降阶算法 被引量:9

Fast Reduction Algorithm for Minimum Vertex Cover Problem
下载PDF
导出
摘要 通过定义判别函数来判别顶点覆盖作用的优劣,得出一个把顶点加入到最小顶点覆盖集的一般化规则,并得出该规则在多种具体情况下的应用定理,在此基础上给出了一个快速降阶算法,该算法能确定某些顶点应该在最小顶点覆盖中,某些顶点不应该在最小顶点覆盖中,达到降低原问题的规模和求解难度的目的.该算法既可以单独使用,又可以与算法结合来达到更好的结果,文中还给出了应用实例及其分析. By defining the discriminant function that can decide the cover effect of two sets of vertex, a generalized rule that can add vertexes into the set of minimum vertex cover was provide. Based on the generalized rule, many applicable theorems that are the special case of the generalized rule were given. Then a fast reduction algorithm was proposed for minimum vertex cover problem. The algorithm can decide which vertexes should be in the optimal solution and which vertexes should not be, so it can reduce the size and difficulty of the problem. The algorithm not only can be used singly, but also can be combined with other algorithms to get better solutions. Series of examples and instances are solved and analyzed.
出处 《小型微型计算机系统》 CSCD 北大核心 2008年第7期1282-1285,共4页 Journal of Chinese Computer Systems
基金 国家自然科学基金项目(70471065)资助 上海市高校选拔培养优秀青年教师科研专项基金项目(21012)资助 上海市教委科技发展基金项目(05EZ31)资助 上海市重点学科建设项目(T0502)资助
关键词 最小顶点覆盖问题 降阶算法 完全图 minimum vertex cover problem reduction algorithm degree complete graph
  • 相关文献

参考文献7

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

二级参考文献12

  • 1GAREY MR, JOHNSON DS. Strong NP-completeness results: motivation, examples, and implications[J]. Journal of ACM, 1978, 25(3): 499 -508.
  • 2KARP R. Reducibility among combinatorial problems[A]. MILLER RE, THATCHER JW, eds. Complexity of Computer Computations[C]. Plenum Press, NY, 1972.85 - 103.
  • 3CORMEN TH, LEISERSON CE, RIVEST RL, et al. Introduction to Algorithms[M]. Second Edition. The MIT Press, 2001.1024-1027, 1040 - 1043.
  • 4BAR-YEHUDA R, EVEN S. A local-ratio theorem for approximating the weighted vertex cover problem[J]. Annals of Discrete Mathematics, 1985, 25:27-46.
  • 5MONIEN B, SPECKENMEYER E. Ramsey numbers and an approximation algorithm for the vertex cover problem[J]. Acta Informatica, 1985,22(1) : 115 - 123.
  • 6HALPERIN E. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs[A]. Proc. 11th Ann[C].ACM-SIAM Symposium on Discrete Algorithms, 2000. 329-337.
  • 7HALPERIN E . Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs[J]. SIAM J. on Computing. 2002.31 (5): 1608 - 1623.
  • 8KARAKOSTAS G. A better approximation ratio for the Vertex Cover problem[R]. ECCC Report TR04-084, 2004.
  • 9HaSTAD J. Some optimal inapproximability results[A]. Proc. 29th Ann[C]. ACM Symp. on Theory of Comp, ACM, 1997.1 - 10.
  • 10DINUR I, SAFRA S. On the importance of being biased( 1.36 hardness of approximating Vertex-Cover)[A]. Annals of Mathematics, to aooear. Also in Proc. of 34th STOC[C]. 2002.

共引文献5

同被引文献44

引证文献9

二级引证文献24

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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