A new approximation algorithm for the weighted vertex cover problem

  • Sushil Chandra Dimri
  • Umesh Kumar Tiwari
  • Mangey Ram

Abstract

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.

Published
2020-02-26