An Algorithm for Minimum Vertex Cover Based on Max-I Share Degree
|
| Title | An Algorithm for Minimum Vertex Cover Based on Max-I Share Degree |
| Authors | |
| Abstract | 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. |
| Publisher | ACADEMY PUBLISHER |
| Date | 2011-08-01 |
| Source | Journal of Computers Vol 6, No 8 (2011): Special Issue: Swarm Intelligent Systems: Theory and Applications |
| Rights | Copyright © ACADEMY PUBLISHER - All Rights Reserved.To request permission, please check out URL: http://www.academypublisher.com/copyrightpermission.html. |