Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6857589 | Information Sciences | 2015 | 11 Pages |
Abstract
The problems to find attribute reduction in rough sets and to obtain the minimal vertex cover for graphs are both NP-hard problems. This paper studies the relationship between the two problems. The vertex cover problem for graphs from the perspective of rough sets is first investigated. The attribute reduction of an information system is then studied in the framework of graph theory. The results in this paper show that finding the minimal vertex cover of a graph is equivalent to finding the attribute reduction of an information system induced from the graph. Conversely, the attribute reduction computation can be translated into the calculation of the minimal vertex cover of a derivative graph. Finally, a new algorithm for the vertex cover problem based on rough sets is presented. Furthermore, experiments are conducted to verify the effectiveness of the proposed method.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Jinkun Chen, Yaojin Lin, Guoping Lin, Jinjin Li, Zhouming Ma,