文章基本信息

标题：An Algorithm for Minimum Vertex Cover Based on Max-I Share Degree
本地全文：下载
作者：Li, Shaohua ; Wang, Jianxin ; Chen, Jianer 等
期刊名称：Journal of Computers
印刷版ISSN：1796-203X
出版年度：2011
卷号：6
期号：8
页码：1781-1788
DOI：10.4304/jcp.6.8.1781-1788
语种：English
出版社：Academy Publisher
摘要：Minimum vertex cover problem(Min-VC) on a graph is a NP-hard problem. The neighborhoods of a vertex are analyzed in this paper, and so are the information they hold for judging whether the vertex is belong to Min-VC or not. Then, the concept of Max-I share degree is put forword in order to qualify the possibility of a vertex to be collected into Min-VC. Based on Max-I share degree, a heuristic algorithm is proposed. Our algorithm has two remarkable characteristics: one is that it is able to get almost the same Min-VC as that of an exact algorithm, and the approximation degree is obviously better than that of other approximation algorithms; the other is that it has polynomial time complexity. Emulational results show that the running time is significantly less than those of other algorithms.
关键词：vertex cover;share degree;approximation degree;heuristic algorithm