A restart local search algorithm with Tabu method for the minimum weighted connected dominating set problem

Abstract

The minimum weighted connected dominating set problem is a significant NP-hard problem with wide applications, and is an extension of the classical minimum dominating set problem. In order to solve this problem, we present a restart local search algorithm with tabu method (RLS$\_$ Tabu). In our RLS$\_$ Tabu algorithm, we firstly involve the random restart initialization method to jump out of the local optimum. Meanwhile, RLS$\_$ Tabu algorithm also applies tabu method in neighborhood search procedure to mitigate the cycling problem. Secondly, we present two strategies in neighborhood search procedure for removing vertices properly, which one is greedy and random strategy, and another one is multiple deletion strategy. The two strategies are crucial to improve the solution quality. Thirdly, the solution connected vertex is important to guarantee the feasibility of solutions. Therefore, we maintain the solution connected vertex set during the neighborhood search, and select the vertex to be added from this set. Finally, in order to intensify the solution, RLS$\_$ Tabu utilizes the pruning function to delete redundant vertices in the candidate solution. In experimental section, we will compare our algorithm with the other six algorithms on three types of benchmarks. Experimental results indicate that our algorithm significantly outperforms the comparative algorithms on most benchmark instances.

Keywords:

• Restart local search
• minimum weighted connected dominating set
• solution
• connected vertex set
• pruning function

Disclosure statement

The authors declare no conflict of interest.

Additional information

Funding

This work was supported by National Natural Science Foundation of China (NSFC) under Grant No. 61806082, 61972063, 61976050, the National Social Foundation of China under Grant No. 19BJY246, 20BTJ062 and the Fundamental Research Funds for the Central Universities , JLU, No.93k172021k07 and NENU, No.2412020QD008.

Notes on contributors

Ruizhi Li

Software, Ruizhi Li and Yupan Wang; methodology, Ruizhi Li and Huan Liu; writing original draft preparation, Ruiting Li and Yupan Wang; writing review and edit, Minghao Yin, Shuli Hu and Ruiting Li.

Yupan Wang

Software, Ruizhi Li and Yupan Wang; methodology, Ruizhi Li and Huan Liu; writing original draft preparation, Ruiting Li and Yupan Wang; writing review and edit, Minghao Yin, Shuli Hu and Ruiting Li.

Huan Liu

Software, Ruizhi Li and Yupan Wang; methodology, Ruizhi Li and Huan Liu; writing original draft preparation, Ruiting Li and Yupan Wang; writing review and edit, Minghao Yin, Shuli Hu and Ruiting Li.

Ruiting Li

Software, Ruizhi Li and Yupan Wang; methodology, Ruizhi Li and Huan Liu; writing original draft preparation, Ruiting Li and Yupan Wang; writing review and edit, Minghao Yin, Shuli Hu and Ruiting Li.

Shuli Hu

Software, Ruizhi Li and Yupan Wang; methodology, Ruizhi Li and Huan Liu; writing original draft preparation, Ruiting Li and Yupan Wang; writing review and edit, Minghao Yin, Shuli Hu and Ruiting Li.

Minghao Yin

Software, Ruizhi Li and Yupan Wang; methodology, Ruizhi Li and Huan Liu; writing original draft preparation, Ruiting Li and Yupan Wang; writing review and edit, Minghao Yin, Shuli Hu and Ruiting Li.