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

References

• Ambühl, C., Erlebach, T., Mihalák, M., & Nunkesser, M. (2006). Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques (pp. 3–14). Springer.
   Google Scholar
• Asavathiratham, C., Roy, S., Lesieutre, B., & Verghese, G. (2001). The influence model. IEEE Control Systems Magazine, 21(6), 52–64.
   Web of Science ®Google Scholar
• Bouamama, S., Blum, C., & Fages, J.-G. (2019). An algorithm based on ant colony optimization for the minimum connected dominating set problem. Applied Soft Computing, 80, 672–686. https://doi.org/10.1016/j.asoc.2019.04.028
   Web of Science ®Google Scholar
• Butenko, S., Oliveira, C., & Pardalos, P. M. (2003). A new algorithm for the minimum connected dominating set problem on ad hoc wireless networks. Proceedings of CCCT’03, 39–44.
   Google Scholar
• Cheng, X., Ding, M., Du, D. H., & Jia, X. (2006). Virtual backbone construction in multihop ad hoc wireless networks. Wireless Communications & Mobile Computing, 6(2), 183–190. https://doi.org/10.1002/wcm.378
   Web of Science ®Google Scholar
• Dagdeviren, Z. A., Aydin, D., & Cinsdikici, M. (2017). Two population-based optimization algorithms for minimum weight connected dominating set problem. Applied Soft Computing, 59, 644–658. https://doi.org/10.1016/j.asoc.2017.06.023
   Web of Science ®Google Scholar
• Datta, T., Srinidhi, N., Chockalingam, A., & Rajan, B. S. (2010). Random-restart reactive tabu search algorithm for detection in large-mimo systems. IEEE Communications Letters, 14(12), 1107–1109. https://doi.org/10.1109/LCOMM.2010.101210.101587
   Web of Science ®Google Scholar
• Ding, M., Cheng, X., & Xue, G. (2003). Aggregation tree construction in sensor networks [Paper presentation]. In 2003 IEEE 58th Vehicular Technology Conference. VTC 2003-Fall (IEEE Cat. No. 03CH37484) (Vol. 4, pp. 2168–2172).
   Google Scholar
• Feo, T. A., & Resende, M. G. (1989). A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 8(2), 67–71. https://doi.org/10.1016/0167-6377(89)90002-3
   Web of Science ®Google Scholar
• Fu, Z., Ren, K., Shu, J., Sun, X., & Huang, F. (2016). Enabling personalized search over encrypted outsourced data with efficiency improvement. IEEE Transactions on Parallel & Distributed Systems, 27(9), 2546–2559. https://doi.org/10.1109/TPDS.2015.2506573
   Web of Science ®Google Scholar
• Garey, M. R., & Johnson, D. S. (1979). Computers and intractability.
   Google Scholar
• Glover, F. (1989). Tabu search—part. Orsa Journal on Computing, 1(3), 190–206. https://doi.org/10.1287/ijoc.1.3.190
   Google Scholar
• Glover, F. (2000). Multi-start and strategic oscillation methods—Principles to exploit adaptive memory. In Computing tools for modeling, optimization and simulation (pp. 1–23). Springer.
   Google Scholar
• Glover, F., & Laguna, M. (1998). Tabu search. In Handbook of combinatorial optimization (pp. 2093–2229). Springer.
   Google Scholar
• Guha, S., & Khuller, S. (1998). Approximation algorithms for connected dominating sets. Algorithmica, 20(4), 374–387. https://doi.org/10.1007/PL00009201
   Web of Science ®Google Scholar
• Hanafi, S., & Freville, A. (1998). An efficient tabu search approach for the 0–1 multidimensional knapsack problem. European Journal of Operational Research, 106(2–3), 659–675. https://doi.org/10.1016/S0377-2217(97)00296-8
   Web of Science ®Google Scholar
• Hedar, A.-R., Ismail, R., El-Sayed, G. A., & Khayyat, K. M. J. (2019). Two meta-heuristics designed to solve the minimum connected dominating set problem for wireless networks design and management. Journal of Network & Systems Management, 27(3), 647–687. https://doi.org/10.1007/s10922-018-9480-1
   Web of Science ®Google Scholar
• Houck, C. R., Joines, J. A., & Kay, M. G. (1996). Comparison of genetic algorithms, random restart and two-opt switching for solving large location–allocation problems. Computers & Operations Research, 23(6), 587–596. https://doi.org/10.1016/0305-0548(95)00063-1
   Web of Science ®Google Scholar
• Hu, S., Li, R., Zhao, P., & Yin, M. (2018). A hybrid metaheuristic algorithm for generalized vertex cover problem. Memetic Computing, 10(2), 165–176. https://doi.org/10.1007/s12293-016-0216-z
   Web of Science ®Google Scholar
• Jovanovic, R., & Tuba, M. (2013). Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set problem. Computer Science & Information Systems, 10(1), 133–149. https://doi.org/10.2298/CSIS110927038J
   Web of Science ®Google Scholar
• Laguna, M., & Marti, R. (1999). Grasp and path relinking for 2-layer straight line crossing minimization. INFORMS Journal on Computing, 11(1), 44–52. https://doi.org/10.1287/ijoc.11.1.44
   Web of Science ®Google Scholar
• Li, R., Hu, S., Cai, S., Gao, J., Wang, Y., & Yin, M. (2020). Numwvc: A novel local search for minimum weighted vertex cover problem. Journal of the Operational Research Society, 71(9), 1498–1509. https://doi.org/10.1080/01605682.2019.1621218
   Web of Science ®Google Scholar
• Li, R., Hu, S., Gao, J., Zhou, Y., Wang, Y., & Yin, M. (2017). Grasp for connected dominating set problems. Neural Computing & Applications, 28(S1), 1059–1067. https://doi.org/10.1007/s00521-016-2429-y
   Web of Science ®Google Scholar
• Li, R., Hu, S., Liu, H., Li, R., Ouyang, D., & Yin, M. (2019). Multi-start local search algorithm for the minimum connected dominating set problems. Mathematics, 7(12), 1173. https://doi.org/10.3390/math7121173
   Web of Science ®Google Scholar
• Li, R., Hu, S., Wang, Y., & Yin, M. (2017). A local search algorithm with tabu strategy and perturbation mechanism for generalized vertex cover problem. Neural Computing and Applications, 28(7), 1775–1785. https://doi.org/10.1007/s00521-015-2172-9
   Web of Science ®Google Scholar
• Li, R., Hu, S., Zhao, P., Zhou, Y., & Yin, M. (2017). A novel local search algorithm for the minimum capacitated dominating set. Journal of the Operational Research Society, 69(6), 849–863.
   Web of Science ®Google Scholar
• Li, R., Liu, H., Wu, X., Wu, J., & Yin, M. (2018). An efficient local search algorithm for the minimum k-dominating set problem. IEEE Access, 6, 62062–62075.
   Web of Science ®Google Scholar
• Li, R., Wu, X., Liu, H., Wu, J., & Yin, M. (2018). An efficient local search for the maximum edge weighted clique problem. IEEE Access, 6, 10743–10753. https://doi.org/10.1109/ACCESS.2018.2799953
   Web of Science ®Google Scholar
• Li, B., Zhang, X., Cai, S., Lin, J., Wang, Y., Blum, C. (2020). Nucds: An efficient local search algorithm for minimum connected dominating set. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence IJCAI-20 (pp. 11–17).
   Google Scholar
• Marques-Silva, J. P., & Sakallah, K. A. (1999). Grasp: A search algorithm for propositional satisfiability. IEEE Transactions on Computers, 48(5), 506–521. https://doi.org/10.1109/12.769433
   Web of Science ®Google Scholar
• Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11), 1097–1100. https://doi.org/10.1016/S0305-0548(97)00031-2
   Web of Science ®Google Scholar
• Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., & Ko, K. (2004). A greedy approximation for minimum connected dominating sets. Theoretical Computer Science, 329(1–3), 325–330. https://doi.org/10.1016/j.tcs.2004.08.013
   Web of Science ®Google Scholar
• Shin, K., Jung, J., Lee, S., & Kang, U. (2015). Bear: Block elimination approach for random walk with restart on large graphs [Paper presentation]. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (pp. 1571–1585).
   Google Scholar
• Shyu, S. J., Yin, P.-Y., & Lin, B. M. (2004). An ant colony optimization algorithm for the minimum weight vertex cover problem. Annals of Operations Research, 131(1–4), 283–304. https://doi.org/10.1023/B:ANOR.0000039523.95673.33
   Web of Science ®Google Scholar
• Simonetti, L., Da Cunha, A. S., Lucena, A. (2011). The minimum connected dominating set problem: Formulation, valid inequalities and a branch-and-cut algorithm. In International Conference on Network Optimization (pp. 162–169).
   Google Scholar
• Torkestani, J. A., & Meybodi, M. R. (2012). Finding minimum weight connected dominating set in stochastic graph based on learning automata. Information Sciences, 200, 57–77. https://doi.org/10.1016/j.ins.2012.02.057
   Web of Science ®Google Scholar
• Tseng, Y., Ni, S., Chen, Y., & Sheu, J. (2002). The broadcast storm problem in a mobile ad hoc network. Wireless Networks, 8(2/3), 153–167. https://doi.org/10.1023/A:1013763825347
   Web of Science ®Google Scholar
• Wang, Y., Cai, S., Yin, M. (2016). Two efficient local search algorithms for maximum weight clique problem. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 30).
   Google Scholar
• Wang, Y., Li, R., Zhou, Y., & Yin, M. (2017). A path cost-based grasp for minimum independent dominating set problem. Neural Computing & Applications, 28(S1), 143–151. https://doi.org/10.1007/s00521-016-2324-6
   Web of Science ®Google Scholar
• Wang, Y., Yin, M., Ouyang, D., & Zhang, L. (2017). A novel local search algorithm with configuration checking and scoring mechanism for the set k-covering problem. International Transactions in Operational Research, 24(6), 1463–1485. https://doi.org/10.1111/itor.12280
   Web of Science ®Google Scholar
• Wang, L., Zhou, T., Wu, X., & Lü, Z. (2016). Variable-depth neighborhood search algorithm for the minimum-connected dominating-set problem. Scientia Sinica Informations, 46(4), 445–460.
   Google Scholar
• Wen, X., Shao, L., Xue, Y., & Fang, W. (2015). A rapid learning algorithm for vehicle classification. Information Sciences, 295, 395–406. https://doi.org/10.1016/j.ins.2014.10.040
   Web of Science ®Google Scholar
• Wu, J., & Dai, F. (2003). Broadcasting in ad hoc networks based on self-pruning. International Journal of Foundations of Computer Science, 14(02), 201–221. https://doi.org/10.1142/S0129054103001686
   Google Scholar
• Wu, X., Lü, Z., & Galinier, P. (2017). Restricted swap-based neighborhood search for the minimum connected dominating set problem. Networks, 69(2), 222–236. https://doi.org/10.1002/net.21728
   Web of Science ®Google Scholar
• Wu, J., & Li, H. (1999). On calculating connected dominating set for efficient routing in ad hoc wireless networks [Paper presentation]. Proceedings of the 3rd International Workshop in on Discrete Algorithms and Methods for Mobile Computing and Communications (pp. 7–14). ACM. https://doi.org/10.1145/313239.313261
   Google Scholar
• Xia, Z., Wang, X., Sun, X., & Wang, B. (2014). Steganalysis of least significant bit matching using multi-order differences. Security & Communication Networks, 7(8), 1283–1291. https://doi.org/10.1002/sec.864
   Web of Science ®Google Scholar
• Xia, Z., Wang, X., Sun, X., & Wang, Q. (2016). A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data. IEEE Transactions on Parallel & Distributed Systems, 27(2), 340–352. https://doi.org/10.1109/TPDS.2015.2401003
   Web of Science ®Google Scholar
• Zou, F., Wang, Y., Xu, X.-H., Li, X., Du, H., Wan, P., & Wu, W. (2011). New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. Theoretical Computer Science, 412(3), 198–208. https://doi.org/10.1016/j.tcs.2009.06.022
   Web of Science ®Google Scholar