An Articulation Point Based Heuristic Algorithm for Minimum Weight Vertex Cover Problem

The minimum weight vertex cover problem (MWVCP) is well known combinatorial optimization problem that has several practical applications and formally defined as: Given an undirected graph with a set of vertices and edges, each vertex is assigned bya positive weight, the MWVCP aims to find a least cardinality subset of vertices with minimum overall weights such that at least one end vertex of each and every edge of the graph belonging to the subset. As MWVCP is NP-hard, most of the studies on it pays attention on heuristic approaches. In this paper, we propose an articulation point/cut vertex based approximation algorithm for solving MWVCP effectively. An illustrative exampleis givento describe the proposed approach. A simple comparative study is performed on different graphs available in the literature. The comparative results show that the proposed algorithm outperforms in providing promising results