Computing-Based Performance Analysis of Approximation Algorithms for the Minimum Weight Vertex Cover Problem of Graphs

Satoshi TAOKA  Daisuke TAKAFUJI  Toshimasa WATANABE  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E96-A   No.6   pp.1331-1339
Publication Date: 2013/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E96.A.1331
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Circuit, System, and Computer Technologies)
vertex covers,  minimum weight vertex cover problem,  approximation algorithms,  computing experiment,  

Full Text: PDF>>
Buy this Article

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. We propose simple procedures as postprocessing of algorithms for MWVC. Furthremore, five existing approximation algorithms with/without the proposed procedures incorporated are implemented, and they are evaluated through computing experiment.