最小顶点覆盖快速降阶算法  

Fast Reduction Algorithm for Minimum Vertex Cover Problem

作　　者：宁爱兵[1] 马良[1] 熊小华[2] 

机构地区：[1]上海理工大学管理学院,上海200093 [2]上海第二工业大学计算机与信息学院,上海201209

出　　处：《小型微型计算机系统》2008年第7期1282-1285,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(70471065)资助;上海市高校选拔培养优秀青年教师科研专项基金项目(21012)资助;上海市教委科技发展基金项目(05EZ31)资助;上海市重点学科建设项目(T0502)资助

摘　　要：通过定义判别函数来判别顶点覆盖作用的优劣,得出一个把顶点加入到最小顶点覆盖集的一般化规则,并得出该规则在多种具体情况下的应用定理,在此基础上给出了一个快速降阶算法,该算法能确定某些顶点应该在最小顶点覆盖中,某些顶点不应该在最小顶点覆盖中,达到降低原问题的规模和求解难度的目的.该算法既可以单独使用,又可以与算法结合来达到更好的结果,文中还给出了应用实例及其分析.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.

关 键 词：最小顶点覆盖问题 降阶算法 度 完全图 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]