###### Abstract  
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. This method can reduce the size of the original graph and thus obtain a high-quality initial solution. Second, we propose an approach based on a two-level configuration checking strategy and a tabu strategy to reduce the cycling problem. Third, we introduce a perturbation strategy and a vertex weighting strategy to help the algorithm be able to jump out of the local optimum effectively. Fourth, we combine the scoring functions _Cscore_ and _Mscore_ with the aforementioned strategies to propose effective methods for selecting vertices. These methods assist the algorithm in selecting vertices that are suitable for addition to or removal from the current candidate solution. Finally, we verify the performance advantages of the local search algorithm by comparing it with existing optimal heuristic algorithms on two sets of instances. The experimental results show that the algorithm exhibits better performance on two sets of classical instances. p 1 2024 18 June 2024 6 July 2024 6 July 2024 18 July 2024 18 July 2024 18 June 2024 6 July 2024 18 July 2  
network nodes can be achieved by communicating with the nodes within the dominating set. Therefore, the MCDS plays a crucial role in practical applications, serving as an effective means to address many challenges in wireless sensor networks by optimizing resource utilization, enhancing network efficiency, and ensuring long-term operational capability. Currently, numerous scholars have extensively researched the MCDS problem and proposed various algorithms to address it. These algorithms fall primarily into two categories: approximation algorithms and heuristic algorithms. Approximation algorithms compromise between computational complexity and exact solution attainment. While exact optimal solutions for many NP-hard problems are challenging to find within polynomial time, approximation algorithms can yield sub-optimal solutions that are close to optimal in a reasonable time frame. Heuristic algorithms, on the other hand, excel at finding satisfactory solutions quickly, making them especially suitable for tackling large and intricate problems. For NP-hard problems or other complex optimization challenges, the careful design of heuristic functions guides the search process, aiding in escaping local optimums and achieving convergence to high-quality solutions more rapidly. Consequently, heuristic algorithms are capable of generating near-optimal solutions within polynomial time. For approximate algorithms, [PERSON] et al. [8] proposed a new greedy approximation algorithm for solving the MCDS problem. The performance ratio is \(\ln(\Delta)+2\), where \(\Delta\) represents the maximum degree of the input graph. Unlike all previously known one-step greedy algorithms with similar performance ratios, the greedy potential function of this algorithm is not supermodular. This implies that the performance analysis method of this new algorithm differs from previous methods based on supermodular potential functions, making it innovative. [PERSON] et al. [9] presented a self-stabilizing algorithm applicable to wireless ad hoc networks and sensor networks aimed at finding MCDS while ensuring safe convergence properties. This algorithm is applied in network environments modeled by unit disk graphs to address the problem of constructing a virtual backbone network due to the absence of fixed infrastructure and centralized management. [PERSON] et al. [10] proposed a greedy approximation algorithm for the MWCDS with labeling (Min-CDSL) problem. Min-CDSL introduces an additional constraint on top of the classical Min-CDS problem, requiring a reduction in the number of distinct labels in the dominating set while considering its size.