期刊
INFORMATION SCIENCES
卷 325, 期 -, 页码 87-97出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2015.07.008
关键词
Attribute reduction; Vertex covers; Graph theory; Rough sets
资金
- National Natural Science Foundation of China [61379021, 61303131, 11301367, 11061004]
- Department of Education of Fujian Province [JK2013027, JK2011031, JA13202, JA11171, JA14192]
- Natural Science Foundation of Fujian Province [2013J01028, 2013J01029, 2012D141, 2013J01265]
- Science Foundation of Minnan Normal University in China [SJ1015]
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. (C) 2015 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据