Test-cost-sensitive rough set based approach for minimum weight vertex cover problem

The minimum vertex cover problem (MVCP) and minimum weighted vertex cover problem (MWVCP) have been used in a variety of applications. This paper focuses on a view of test-cost-sensitive rough set for MWVCP. We first provide a method to convert a minimum weight vertex cover of a graph into a minimal test cost attribute reduct of a test-cost-sensitive decision table. Then, an induced test-cost-sensitive decision table from an undirected weighted graph is established. On the foundation of the induced decision table, an improved heuristic algorithm for finding minimum weight vertex covers is proposed, it can avoid a mass of redundant computation. Furthermore, to improve efficiency, a quantum-behaved particle swarm optimization with immune mechanism is presented, which can avoid the phenomenon of premature, improve the global searching ability, and enhance the convergence speed. The results of the experiment show the advantages and limitations of the proposed algorithms compared with state-of-the-art algorithms.