To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
A Simple and Efficient Algorithm for Optimization of Minimum Vertex Cover Problem |
|
Author |
Aslam Khan and Said Khalid Shah |
| Citation |
Vol. 26 No. 5 pp. 90-98 |
|
Abstract |
This paper represent a very simple and efficient Polynomial time and Maximum degree contribution algorithm (MDCA). The proposed algorithm consists of three parts, first the degree of each vertex is calculated and it is checked as there a vertex having degree equal to 1, if yes then the neighbor of that vertex is added to MVC. If more than one vertex having degree equal to ‘1’ then randomly one of them is selected and the neighbor of that vertex is added to MVC. In second step, If G= (V, E) have no vertex having degree equal to 1 then the vertex having maximum degree in the given graph (G) and its neighbors are determined. The edges are removed one by one of the maximum degree vertex, first that vertex is removed which is attached to the minimum degree vertex, if the degree of that minimum degree vertex becomes ‘1’then its neighbor is added to MVC. The edges between maximum degree vertex and its neighbors are removed one by one by starting from the minimum degree neighbor vertex and after removing all edges and the degree of maximum degree vertex become ‘0’ then the maximum degree vertex itself is added to MVC. This whole process continues until the graph becomes empty. This algorithm is tested on small as well as on large bench mark instances. The experimental results and the comparative analysis show that MDCA gives better and fast solution as compare to others approximation algorithms found in the literature for solving minimum vertex cover problem. |
|
Keywords |
Minimum vertex cover (MVC); maximum independent set (MIS); NP ?complete problem; optimization problem; approximation algorithm; maximum degree greedy (MDG); advanced Vertex Support Algorithm(AVSA);Modified Vertex Support Algorithm(MVSA); and maximum degre |
|
URL |
