Affiliations: [a] School of Computer Science, Minnan Normal University, Zhangzhou, China
| [b] School ofMathematics, Physics and Information Science, Zhejiang Ocean University, Zhoushan, China
| [c] Key Laboratory of Oceanographic Big Data Mining and Application of Zhejiang Province, Zhoushan, China
| [d] School of Mathematicsand statistics, Minnan Normal University, Zhangzhou, China
Abstract: In this paper, we first establish a Multi-Relation Granular Computing model by a given graph, and point out that all the reducts of the constructed Multi-Relation Granular Computing model are exactly all the minimal vertex covers of the corresponding graph. Thus, the vertex cover problem in graph theory can be converted to the knowledge reduction problem in rough set theory. Based on the conversion, we then introduce methods for dealing with the knowledge reduction problem to solve the vertex cover problem. In particular, we introduce a kind of method called the heuristic reduction algorithm based on entropy.
