Affiliation of Author(s):计算机科学与技术学院/人工智能学院/软件学院

Journal:APPLIED SOFT COMPUTING

Key Words:Rough set Attribute reduction Minimum weight vertex cover Graph theory

Abstract: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. (C) 2017 Elsevier B.V. All rights reserved.

ISSN No.:1568-4946

Translation or Not:no

Date of Publication:2018-03-01

Co-author:Xie, Xiaojun,Yu, Chunqiang,Xu, Xingye

Correspondence Author:qxz