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

被引：0
作者：
Shengyang Zhuang
Degang Chen
机构：
[1] North China Electric Power University,School of Mathematics and Physics
来源：
International Journal of Machine Learning and Cybernetics | 2019年 / 10卷
关键词：
Vertex cover; Attribute reduction; Discernibility matrix; Minimal element;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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
页数：7
相关论文
共 74 条
[1]  
Sáenz-de Cabezón E(2014)Measuring the robustness of a network using minimal vertex covers Math Comput Simulation 104 82-94
[2]  
Wynn HP(2014)Attribute reduction for heterogeneous data based on the combination of classical and fuzzy rough set models IEEE Trans Fuzzy Syst 22 1325-1334
[3]  
Chen D(2012)Sample pair selection for attribute reduction with rough set IEEE Trans Knowl Data Eng 11 2080-2093
[4]  
Yang YY(2012)An application of rough sets to graph theory Inf Sci 201 114-127
[5]  
Chen D(2016)A rough set method for the minimum vertex cover problem of graphs Appl Soft Comput 42 360-367
[6]  
Zhao S(2015)The relationship between attribute reducts in rough sets and minimal vertex covers of graphs Inf Sci 325 87-97
[7]  
Zhang L(1979)A greedy heuristic for the set-covering problem Math Oper Res 4 233-235
[8]  
Yang Y(2007)A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets Inf Sci 177 3500-3518
[9]  
Zhang X(1995)Identifying the minimal transversals of a hypergraph and related problems SIAM J Comput 24 1278-1304
[10]  
Chen J(2006)Experimental analysis of approximation algorithms for the vertex cover and set covering problems Comput Oper Res 33 3520-3534
12345678