## 6 Conclusions  
In this paper, a new local search algorithm named PCC\({}^{2}\)LS is proposed for solving the minimum connected dominating set problem. In the initial solution construction stage, three simplification rules are proposed to simplify the original graph. A combination of vertex weighting, perturbation, two-level configuration checking, and tabu strategies are used to avoid cyclic search and falling into local optimum. These methods ensure that the algorithm has good adaptability and stability in the face of different instance inputs and can find high-quality solutions even for NP-hard problems, which shows that the algorithm has good robustness. The design of the vertex weighting strategy makes the algorithm tend to select the vertices that have not changed their states for a long time, which increases the diversity and possibility of solution space exploration. Meanwhile, the perturbation strategy can effectively jump out of the local optimal solutions, which further promotes the generation of different solutions. Based on the above strategies and properties, a meta-heuristic local search algorithm PCC\({}^{2}\)LS is designed and compared with six state-of-the-art local search algorithms, namely, greedy, ACO, ACO + PCS, GRASP, VDNS, and MSLS, and the experimental results show that, on a number of benchmark instances, the proposed PCC\({}^{2}\)LS algorithm is able to find better solutions compared with the other compared algorithms or the known best solutions than the other comparative algorithms, showing higher solution quality. Specifically, the PCC\({}^{2}\)LS algorithm is able to find the known best solution on LPNMR'09 instances and obtain new upper bounds for 13 best solutions and 27 average solutions on common UDG instances. In terms of solution time, the PCC\({}^{2}\)LS algorithm is able to find the best solution in a relatively short time (less than 30 s on average) on most of the benchmark instances, especially for the smallerinstances. Even for large-scale instances, the solution can be completed in a reasonable time (usually under 70 s) in most cases. In the future, our proposed algorithmic framework can also be adapted to tackle other combinatorial optimization problems, including but not limited to the minimum vertex cover problem [22], and the set-union knapsack problem [23; 24]. Ongoing belief suggests that there is still room for improvement when addressing large-scale graph instances. For example, we can employ parallel local search algorithms based on CUDA (Compute Unified Device Architecture) [25] to solve some combinatorial optimization problems. We can utilize the CUDA framework to increase processing speed by distributing computationally intensive tasks to multiple cores of the GPU for parallel execution. As a result, we continually explore other strategies to further enhance the PCC\({}^{2}\)LS algorithm and effectively solve a greater number of large-scale graph instance problems. Meanwhile, we plan to extend the PCC\({}^{2}\)LS algorithm to more practical scenarios, such as social network analysis, gene regulatory networks in bioinformatics, and transportation network planning. By applying the algorithms in these specific domains, we aim to validate their generality and practicality. In addition, we will also customize the algorithm to improve it according to the needs of different applications in order to better solve practical problems. Conceptualization, J.H., S.H. and M.Y. ; methodology, R.L. and J.H. ; software, J.H. and S.L. ; validation, R.L. ; formal analysis, J.H. and M.Y. ; resources, M.Y. ; data curation, J.H., S.L., S.H. and M.Y. ; writing--original draft preparation, R.L. and J.H. ; writing--review and editing, R.L., S.L. and S.H. ; visualization, J.H. ; supervision, R.L. ; project administration, R.L. and S.H. ; funding acquisition, M.Y. All authors have read and agreed to the published version of the manuscript. This work was supported by the National Natural Science Foundation of China (NSFC) under Grant No.