Page 252 - 《软件学报》2025年第8期

李睿智 等: 局部搜索算法求解最小弱连通支配集问题 3675

[4] Mai VS, La RJ, Battou A. Optimal cybersecurity investments using SIS model: Weakly connected networks. In: Proc. of the 2022 IEEE
Global Communications Conf. Rio de Janeiro: IEEE, 2022. 6097–6102. [doi: 10.1109/GLOBECOM48099.2022.10001358]
[5] Sou KC, Lu J. Relaxed connected dominating set problem for power system cyber-physical security. IEEE Trans. on Control of Network
Systems, 2022, 9(4): 1780–1792. [doi: 10.1109/TCNS.2022.3165088]
[6] Probierz B, Hrabia A, Kozak J. A new method for graph-based representation of text in natural language processing. Electronics, 2023,
12(13): 2846. [doi: 10.1016/j.automatica.2022.11079]
[7] Han B, Jia WJ. Clustering wireless ad hoc networks with weakly connected dominating set. Journal of Parallel and Distributed
Computing, 2007, 67(6): 727–737. [doi: 10.1016/j.jpdc.2007.03.001]
[8] Domke GS, Hattingh JH, Markus LR. On weakly connected domination in graphs II. Discrete Mathematics, 2005, 305(1–3): 112–122.
[doi: 10.1016/j.disc.2005.10.006]
[9] Raczek J, Cyman J. Weakly connected roman domination in graphs. Discrete Applied Mathematics, 2019, 267: 151–159. [doi: 10.1016/j.
dam.2019.05.002]
[10] Sandueta EP. Weakly connected total domination critical graphs. Advances and Applications in Discrete Mathematics, 2020, 25(2):
267–274. [doi: 10.17654/DM025020267]
[11] Chen YZP, Liestman AL. Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks. In:
Proc. of the 3rd ACM Int’l Symposium on Mobile Ad Hoc Networking & Computing. Lausanne: Association for Computing Machinery,
2002. 165–172. [doi: 10.1145/513800.51382]
[12] Dubhashi D, Mei A, Panconesi A, Radhakrishnan J, Srinivasan A. Fast distributed algorithms for (weakly) connected dominating sets and
linear-size skeletons. Journal of Computer and System Sciences, 2005, 71(4): 467–479. [doi: 10.1016/j.jcss.2005.04.002]
[13] Ding YH, Wang JZ, Srimani PK. A linear time self-stabilizing algorithm for minimal weakly connected dominating sets. Int’l Journal of
Parallel Programming, 2016, 44(1): 151–162. [doi: 10.1007/s10766-014-0335-4]
[14] Torkestani JA, Meybodi MR. Learning automata-based algorithms for finding minimum weakly connected dominating set in stochastic
graphs. Int’l Journal of Uncertainty, Fuzziness and Knowledge-based Systems, 2010, 18(6): 721–758. [doi: 10.1142/
S0218488510006775]
[15] Niu DD, Yin MH. A self-stabilizing memetic algorithm for minimum weakly connected dominating set problems. In: Proc. of the 2nd Int’l
Workshop on Heuristic Search in Industry (HSI). 2022.
[16] Niu DD, Nie XL, Zhang LL, Zhang HM, Yin MH. A greedy randomized adaptive search procedure (grasp) for minimum weakly
connected dominating set problem. Expert Systems with Applications, 2023, 215: 119338. [doi: 10.1016/j.eswa.2022.119338]
[17] Albuquerque M, Vidal T. An efficient matheuristic for the minimum-weight dominating set problem. Applied Soft Computing, 2018, 72:
527–538. [doi: 10.1016/j.asoc.2018.06.052]
[18] Li RZ, Hu SL, Liu H, Li RT, Ouyang DT, Yin MH. Multi-start local search algorithm for the minimum connected dominating set
problems. Mathematics, 2019, 7(12): 1173. [doi: 10.3390/math7121173]
[19] Abu-Khzam FA. An improved exact algorithm for minimum dominating set in chordal graphs. Information Processing Letters, 2022, 174:
106206. [doi: 10.1016/j.ipl.2021.106206]
[20] Nakkala MR, Singh A, Rossi A. Swarm intelligence, exact and matheuristic approaches for minimum weight directed dominating set
problem. Engineering Applications of Artificial Intelligence, 2022, 109: 104647. [doi: 10.1016/j.engappai.2021.104647]
[21] Glover F. Tabu search—Part I. ORSA Journal on Computing, 1989, 1(3): 190–206. [doi: 10.1287/ijoc.1.3.190]
[22] Cai SW, Su KL, Sattar A. Local search with edge weighting and configuration checking heuristics for minimum vertex cover. Artificial
Intelligence, 2011, 175(9–10): 1672–1696. [doi: 10.1016/j.artint.2011.03.003]
[23] Li RZ, Hu SL, Zhang HC, Yin MH. An efficient local search framework for the minimum weighted vertex cover problem. Information
Sciences, 2016, 372: 428–445. [doi: 10.1016/j.ins.2016.08.053]
[24] Zhou JP, Ren XL, Yin Q, Li RZ, Yin MH. Algorithm of strengthened configuration checking and clause weighting for solving the
minimum satisfiability problem. Chinese Journal of Computers, 2018, 41(4): 745–759 (in Chinese with English abstract). [doi: 10.11897/
SP.J.1016.2018.00745]
[25] Jovanovic R, Tuba M. Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set
problem. Computer Science and Information Systems, 2013, 10(1): 133–149. [doi: 10.2298/CSIS110927038J]
[26] Li RZ, Wang YP, Liu H, Li RT, Hu SL, Yin MH. A restart local search algorithm with tabu method for the minimum weighted connected
dominating set problem. Journal of the Operational Research Society, 2022, 73(9): 2090–2103. [doi: 10.1080/01605682.2021.1952117]
[27] Tai R, Ouyang DT, Li RZ, Zhang LM. ILSGVCP: An improved local search algorithm for generalized vertex cover problem. Journal of
the Operational Research Society, 2023, 74(11): 2382–2390. [doi: 10.1080/01605682.2022.2147458]