A new approximation algorithm for the weighted vertex cover problem
Sushil Chandra Dimri, Umesh Kumar Tiwari, Mangey Ram · Journal | MESA · 2020
The minimum weighted vertex cover is an acknowledged NP complete problem. If there is an undirected graph G = (V, E) given with weights on every vertex, the challenge is to discover a vertex set C* subset of V, such that vertices belonging to the set C* have minimum weight and should cover each edge belonging to the edge set E. In this work an approximation algorithm for a given graph G = (V, E) is proposed to discover nearest optimal solution of the weighted vertex cover problem. The proposed algorithm is greedy in nature. In this work adjacency matrix is used to represent the graph.