Performance comparison of approximation algorithms for the minimum weight vertex cover problem
Satoshi Taoka, Toshimasa Watanabe · 2012
A vertex cover of a given graph G = (V, E) is a subset N of V such that N contains either u or v for any edge (u, v) of E. The minimum weight vertex cover problem (MWVC for short) is the problem of finding a vertex cover N of any given graph G = (V, E), with weight w(v) for each vertex v of V, such that the sum w(N) of w(v) over all v of N is minimum. In this paper, we consider MWVC with w(v) of any v of V being a positive integer. Five existing approximation algorithms are implemented, and they are evaluated through computing experiment.