A local search method based on edge age strategy for minimum vertex cover problem in massive graphs

作者：

Highlights：

• For undirected graphs, the edge weighting method is simpler and more effective.

• A new method for using edge weights in MVCP is proposed.

• EAVC can find smaller vertex coverage on large real-world massive graphs.

摘要

•For undirected graphs, the edge weighting method is simpler and more effective.•A new method for using edge weights in MVCP is proposed.•EAVC can find smaller vertex coverage on large real-world massive graphs.

论文关键词：Minimum vertex cover,Local search algorithm,Edge weighting,Combinatorial optimization,Heuristic algorithm

论文评审过程：Received 23 February 2020, Revised 9 April 2021, Accepted 8 May 2021, Available online 19 May 2021, Version of Record 25 May 2021.

论文官网地址：https://doi.org/10.1016/j.eswa.2021.115185