A Metaheuristic Algorithm for Vertex Cover based Link Monitoring and Backbone Formation in Wireless Ad hoc Networks

作者：

Highlights：

• A metaheuristic weighted connected vertex cover (WCVC) algorithm is proposed.

• The proposed algorithm is based on the population-based iterated greedy technique.

• The design of the algorithm with example operations is given in detail.

• The time complexity of the algorithm is analyzed.

• The algorithm outperforms its competitors in terms of WCVC weight.

摘要

•A metaheuristic weighted connected vertex cover (WCVC) algorithm is proposed.•The proposed algorithm is based on the population-based iterated greedy technique.•The design of the algorithm with example operations is given in detail.•The time complexity of the algorithm is analyzed.•The algorithm outperforms its competitors in terms of WCVC weight.

论文关键词：Wireless Ad hoc networks,Minimum weighted connected vertex cover,Population-based iterated greedy algorithm,Graph theory,Link monitoring

论文评审过程：Received 20 June 2021, Revised 9 August 2022, Accepted 25 September 2022, Available online 30 September 2022, Version of Record 7 October 2022.

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