一种增量式约简方法求解最小顶点覆盖问题  

Incremental attribute reduction method for minimum vertex cover problem

作　　者：占善华[1] 谢小军 Zhan Shanhua;Xie Xiaojun(Dept.of Information Management,Guangdong Justice Police Vocational College,Guangzhou 510520,China;College of Computer Science ＆ Technology,Nanjing University of Aeronautics ＆ Astronautics,Nanjing 210016,China)

机构地区：[1]广东司法警官职业学院信息管理系,广州510520 [2]南京航空航天大学计算机科学与技术学院,南京210016

出　　处：《计算机应用研究》2018年第12期3685-3688,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(61672171);广东省教育厅重大科研项目(2016KZDXM052)

摘　　要：最小顶点覆盖问题是一个应用很广泛的NP难题,针对该问题给出一种增量式属性约简方法。首先将最小顶点覆盖问题转换为一个决策表的最小属性约简问题;利用增量式属性约简思想,随着图中边数的增多,提出一种更新最小顶点覆盖的增量式属性约简算法;该算法时间复杂度低于计算整个图的最小顶点覆盖的时间复杂度,同时针对大规模图问题,可随着边的增加动态更新最小顶点覆盖,因此降低了属性约简的方法求解最小顶点覆盖问题的运行时间。实验结果表明了该算法的可行性和有效性。The minimum vertex cover problem is NP-complete problem with a wide range of applications. This paper proposed an incremental attribute reduction method for minimum vertex cover problem. Firstly,it transformed the minimum vertex cover problem into a minimum attribute reduction problem of decision table. With the increase of the number of edges in the graph,this paper proposed an incremental attribute reduction algorithm to update the minimum vertex cover of dynamic graph. The time complexity of the algorithm was lower than that of calculating the minimum vertex coverage of the whole graph. For the large-scale graph problem,the minimum vertex cover could be updated with the increase of the edge,so it decreased the running time of attribute reduction method for minimum vertex coverage problem. The experimental results show that the algorithm is feasible and effective.

关 键 词：增量式约简 最小顶点覆盖 最小属性约简 大规模图 

分 类 号：TP391.6[自动化与计算机技术—计算机应用技术]