A novel rough set-based approach for minimum vertex cover of hypergraphs

被引:0
作者
Qian Zhou
Xiaojun Xie
Hua Dai
Weizhi Meng
机构
[1] Nanjing University of Posts and Telecommunications,School of Modern Posts
[2] Nanjing Agricultural University,College of Artificial Intelligence
[3] Nanjing University of Posts and Telecommunications,School of Computer Science
[4] Technical University of Denmark,Department of Applied Mathematics and Computer Science
来源
Neural Computing and Applications | 2022年 / 34卷
关键词
Minimum vertex cover; Hypergraph; Rough set; Attribute reduction;
D O I
暂无
中图分类号
学科分类号
摘要
Minimum vertex covering has been widely used and studied as a general optimization problem. We focus on one of its variation: minimum vertex cover of hypergraphs. Most existed algorithms are designed for general graphs, where each edge contains at most two vertices. Moreover, among these algorithms, rough set-based algorithms have been proposed recently and attract many researchers sight. However, they are not efficient enough when the number of nodes and hyperedges scale largely. To address these limitations, we propose a novel rough set-based approach by combining rough set theory with the stochastic local search algorithm. In this approach, three improvements have been introduced, i.e., (1) fast relative reduct construction method, which can quickly achieve a relative reduct, and it is based on low-complexity heuristics; (2) (p, q)-reverse incremental verification mechanism, which uses incremental positive region update technology to quickly verify whether a required attribute pair can be found; (3) adjusting iterative process rules, the main purposes of these rules are avoiding repeated computation and jumping out of local optimum. Finally, by comparing groups of benchmark graphs and hypergraphs with the existing algorithms based on rough sets, experimental results presents the advantages and limitations of our proposed approach.
引用
收藏
页码:21793 / 21808
页数:15
相关论文
共 87 条
[1]  
Chen J(2001)Vertex cover: further observations and further improvements J Algorithms 41 280-301
[2]  
Kanj IA(2018)An efficient local search for partial vertex cover problem Neural Comput Appl 30 2245-2256
[3]  
Jia W(2017)A local search algorithm with tabu strategy and perturbation mechanism for generalized vertex cover problem Neural Comput Appl 28 1775-1785
[4]  
Zhou Yupeng(2013)Towards a snowdrift game optimization to vertex cover of networks IEEE Trans Cybern 43 948-956
[5]  
Wang Yiyuan(2019)Game-based memetic algorithm to the vertex cover of networks IEEE Trans Cybern 49 974-988
[6]  
Gao Jian(2011)Local search with edge weighting and configuration checking heuristics for minimum vertex cover Artif Intell 175 1672-1696
[7]  
Luo Na(2013)Numvc: an efficient local search algorithm for minimum vertex cover J Artif Intell Res 46 687-716
[8]  
Wang Jianan(2017)Finding a small vertex cover in massive sparse graphs: construct, local search, and preprocess J Artif Intell Res 59 463-494
[9]  
Li Ruizhi(2017)A local search algorithm with tabu strategy and perturbation mechanism for generalized vertex cover problem Neural Comput Appl 28 1775-1785
[10]  
Shuli Hu(2021)A local search method based on edge age strategy for minimum vertex cover problem in massive graphs Exp Syst Appl 182 115185-2256