A rough set method for the minimum vertex cover problem of graphs

作者：Chen, Jinkun^*; Lin, Yaojin^*; Li, Jinjin; Lin, Guoping; Ma, Zhouming; Tan, Anhui

来源：Applied Soft Computing, 2016, 42: 360-367.

DOI：10.1016/j.asoc.2016.02.003

• Attribute reduction
• Decision information tables
• Minimum vertex covers
• Rough set theory

The minimum vertex cover problem is a classical combinatorial optimization problem. This paper studies this problem based on rough sets. We show that finding the minimal vertex cover of a graph can be translated into finding the attribute reduction of a decision information table. At the same time, finding a minimum vertex cover of graphs is equivalent to finding an optimal reduct of a decision information table. As an application of the theoretical framework, a new algorithm for the minimum vertex cover problem based on rough sets is constructed. Experiments show that the proposed algorithm gets better performance in terms of the ratio value when compared with some other algorithms.

• 出版日期2016-5
• 单位厦门大学; 闽南师范大学