A fast heuristic for the minimum weight vertex cover problem

摘要

Given a vertex-weighted undirected graph, to find the vertex cover of minimum weight is called minimum weight vertex cover problem (MWVCP). It is known as an NP-hard problem. In this paper, a fast heuristic for MWVCP is proposed. Our algorithm is based on a simple algorithm called “list-heuristic.” Experimenal results show that our algorithm calculates better solutions in shorter time than approximation algorithms for MWVCP.