Towards faster local search for minimum weight vertex cover on massive graphs
Towards faster local search for minimum weight vertex cover on massive graphs
复制标题
在大规模图上更快地进行最小权重顶点覆盖的本地搜索
DOI：
10.1016/j.ins.2018.08.052
复制
发表时间：
2019-01-01
影响因子：
8.1
通讯作者：
Wang, Haoran
中科院分区：
文献类型：
--
作者：
Cai, Shaowei;Li, Yuanjie;Wang, Haoran
最小权顶点覆盖（MWVC）问题是一个著名的NP-难问题，具有各种实际应用。本文设计了一个高效的算法FastWVC来解决大规模图中的MWVC问题。为此，我们提出了一个构造过程，其目的是在短时间内生成一个质量初始顶点覆盖。我们还提出了一个新的交换步骤，用于重建顶点覆盖。此外，在添加顶点的选择上采用了一种成本有效的策略，从而加快了算法的速度。通过对102个实例的实验验证了算法的有效性。结果表明，FastWVC算法优于其他算法的解决方案的质量和计算时间在大多数情况下。我们还进行实验来分析潜在想法的有效性。(C)2018爱思唯尔公司All rights reserved.
The minimum weight vertex cover (MWVC) problem is a well known NP-hard problem with various real-world applications. In this paper, we design an efficient algorithm named FastWVC to solve MWVC problem in massive graphs. To this end, we propose a construction procedure, which aims to generate a quality initial vertex cover in short time. We also propose a new exchange step for reconstructing a vertex cover. Additionally, a cost-effective strategy is used for choosing adding vertices, which can accelerate the algorithm. Experiments on 102 instances were conducted to confirm the effectiveness of our algorithm. The results show that the FastWVC algorithm outperforms other algorithms in terms of both solution quality and computational time in most of the instances. We also carry out experiments that analyze the effectiveness of the underlying ideas. (C) 2018 Elsevier Inc. All rights reserved.