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 条
[11]  
Li J(1982)Approximation algorithms for the set covering and vertex cover problems SIAM J Comput 11 555-556
[12]  
Chen J(2008)Neighborhood rough set based heterogeneous feature subset selection Inf Sci 178 3577-3594
[13]  
Lin Y(2018)The multi-vehicle probabilistic covering tour problem Eur J Oper Res 271 278-287
[14]  
Li J(2017)Comparison of reduction in formal decision contexts Int J Approx Reason 80 100-122
[15]  
Lin G(2013)Incomplete decision contexts: approximate concept construction, rule acquisition and knowledge reduction Int J Approx Reason 54 149-165
[16]  
Ma Z(2012)The solution algorithms for problems on the minimal vertex cover in networks and the minimal cover in boolean matrixes Int J Comput Sci Issues (IJCSI) 9 8-2060
[17]  
Tan A(2013)Circuit extension and circuit double cover of graphs Discret Math 313 2055-356
[18]  
Chen J(1982)Rough sets Int J Comput Inf Sci 11 341-591
[19]  
Lin Y(2007)Mobility of vertex-transitive graphs Discret Math 307 579-2013
[20]  
Lin G(2016)A rough set method for the vertex cover problem in graph theory J Intell Fuzzy Syst 30 2003-71
12345678