A novel algorithm for the vertex cover problem based on minimal elements of discernibility matrix

被引：2

作者：

Zhuang, Shengyang ^{[1
]}

Chen, Degang ^{[1
]}

机构：

[1] North China Elect Power Univ, Sch Math & Phys, Beijing 102206, Peoples R China

来源：

INTERNATIONAL JOURNAL OF MACHINE LEARNING AND CYBERNETICS | 2019年 / 10卷 / 12期

关键词：

Vertex cover; Attribute reduction; Discernibility matrix; Minimal element; ROUGH SET METHOD; ATTRIBUTE REDUCTION; APPROXIMATION ALGORITHMS; COMBINATION;

D O I：

10.1007/s13042-019-00933-6

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Minimal vertex cover problem (MVCP) is a famous important NP-hard problem in graph theory. It has been reported that MVCP is equivalent to finding reducts of information systems in rough sets theory. This relationship motivates our idea to deal with MVCP in terms of approaches to discernibility matrix in rough set. First we point out that only minimal elements in the discernibility matrix are useful for MVCP, and we present a novel algorithm based on minimal elements for MVCP. Then we make experimental comparisons to demonstrate the effectiveness of this new algorithm on big graphs.

引用

页码：3467 / 3474

页数：8

共 29 条

[1]

[Anonymous], 2012, INT J COMPUT SCI ISS

[2]

[Anonymous], 2007, Graph Theory

[3]

Bondy J. A., 2008, GRAPH THEORY

[4] 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

[5] 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

[6] 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

[7] A rough set method for the minimum vertex cover problem of graphs [J].

Chen, Jinkun ;

Lin, Yaojin ;

Li, Jinjin ;

Lin, Guoping ;

Ma, Zhouming ;

Tan, Anhui .

APPLIED SOFT COMPUTING, 2016, 42 :360-367

[8] The relationship between attribute reducts in rough sets and minimal vertex covers of graphs [J].

Chen, Jinkun ;

Lin, Yaojin ;

Lin, Guoping ;

Li, Jinjin ;

Ma, Zhouming .

INFORMATION SCIENCES, 2015, 325 :87-97

[9] An application of rough sets to graph theory [J].

Chen, Jinkun ;

Li, Jinjin .

INFORMATION SCIENCES, 2012, 201 :114-127

[10]

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

← 1 2 3 →