Abstract: The Maximum Weighted Independent Set (MWIS)
problem is a classic graph optimization NP-hard problem. Given an
undirected graph G = (V, E) and weighting function defined on the
vertex set, the MWIS problem is to find a vertex set S V whose total
weight is maximum subject to no two vertices in S are adjacent. This
paper presents a novel approach to approximate the MWIS of a graph
using minimum weighted vertex cover of the graph. Computational
experiments are designed and conducted to study the performance
of our proposed algorithm. Extensive simulation results show that
the proposed algorithm can yield better solutions than other existing
algorithms found in the literature for solving the MWIS.
Abstract: The Minimum Weighted Vertex Cover (MWVC) problem is a classic graph optimization NP - complete problem. Given an undirected graph G = (V, E) and weighting function defined on the vertex set, the minimum weighted vertex cover problem is to find a vertex set S V whose total weight is minimum subject to every edge of G has at least one end point in S. In this paper an effective algorithm, called Support Ratio Algorithm (SRA), is designed to find the minimum weighted vertex cover of a graph. Computational experiments are designed and conducted to study the performance of our proposed algorithm. Extensive simulation results show that the SRA can yield better solutions than other existing algorithms found in the literature for solving the minimum vertex cover problem.