The relationship between attribute reducts in rough sets and minimal vertex covers of graphs

被引：31

作者：

Chen, Jinkun ^{[1
]}

Lin, Yaojin ^{[2
]}

Lin, Guoping ^{[1
]}

Li, Jinjin ^{[1
]}

Ma, Zhouming ^{[1
]}

机构：

[1] Minnan Normal Univ, Sch Math & Stat, Zhangzhou 363000, Peoples R China

[2] Minnan Normal Univ, Sch Comp Sci, Zhangzhou 363000, Peoples R China

来源：

INFORMATION SCIENCES | 2015年 / 325卷

基金：

中国国家自然科学基金;

关键词：

Attribute reduction; Vertex covers; Graph theory; Rough sets; APPROXIMATION ALGORITHMS; DISCERNIBILITY MATRIX; KNOWLEDGE REDUCTION; FEATURE-SELECTION; INFORMATION; GRANULATION; ENTROPY; COMBINATION; SYSTEMS; MODEL;

D O I：

10.1016/j.ins.2015.07.008

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：87 / 97

页数：11

共 67 条

[1]

[Anonymous], 1972, Complexity of Computer Computations, DOI [10.1007/978-3-540-68279-0-8, DOI 10.1007/978-1-4684-2001-2]

[2]

Bargiela A., 2003, Granular Computing: An Introduction

[3] Resynchronization for multiprocessor DSP systems [J].

Bhattacharyya, SS ;

Sriram, S ;

Lee, EA .

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-FUNDAMENTAL THEORY AND APPLICATIONS, 2000, 47 (11) :1597-1609

[4]

Bondy J. A., 2008, Graph Theory M

[5]

Bondy J. A., 2008, Graph Theory with Applications

[6] Modeling and solving the crew rostering problem [J].

Caprara, A ;

Toth, P ;

Vigo, D ;

Fischetti, M .

OPERATIONS RESEARCH, 1998, 46 (06) :820-830

[7] A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets [J].

Chen Degang ;

Wang Changzhong ;

Hu Qinghua .

INFORMATION SCIENCES, 2007, 177 (17) :3500-3518

[8] Attribute Reduction for Heterogeneous Data Based on the Combination of Classical and Fuzzy Rough Set Models [J].

Chen, Degang ;

Yang, Yanyan .

IEEE TRANSACTIONS ON FUZZY SYSTEMS, 2014, 22 (05) :1325-1334

[9] Sample Pair Selection for Attribute Reduction with Rough Set [J].

Chen, Degang ;

Zhao, Suyun ;

Zhang, Lei ;

Yang, Yongping ;

Zhang, Xiao .

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2012, 24 (11) :2080-2093

[10]

Chvatal V., 1979, Mathematics of Operations Research, V4, P233, DOI 10.1287/moor.4.3.233

← 1 2 3 4 5 6 7 →