A Local Search Algorithm with Vertex Weighting Strategy and Two-Level Configuration Checking for the Minimum Connected Dominating Set Problem.

The minimum connected dominating set problem is a combinatorial optimization problem with a wide range of applications in many fields. We propose an efficient local search algorithm to solve this problem. In this work, first, we adopt a new initial solution construction method based on three simplification rules.