ILSGVCP: An improved local search algorithm for generalized vertex cover problem

References

• Abualigah, L., Abd Elaziz, M., Sumari, P., Geem, Z. W., & Gandomi, A. H. (2022). Reptile search algorithm (rsa): A nature-inspired meta-heuristic optimizer. Expert Systems with Applications, 191, 116158.
   Web of Science ®Google Scholar
• Aggarwal, C. C., Orlin, J. B., & Tai, R. P. (1997). Optimized crossover for the independent set problem. Operations research, 45(2), 226–234.
   Web of Science ®Google Scholar
• Andrade, D. V., Resende, M. G., & Werneck, R. F. (2008). Fast local search for the maximum independent set problem. In International Workshop on Experimental and Efficient Algorithms, pp. 220–234.
   Google Scholar
• Barbosa, V. C., & Campos, L. C. (2004). A novel evolutionary formulation of the maximum independent set problem. Journal of Combinatorial Optimization, 8(4), 419–437.
   Web of Science ®Google Scholar
• Bouamama, S., Blum, C., & Boukerram, A. (2012). A population-based iterated greedy algorithm for the minimum weight vertex cover problem. Applied Soft Computing, 12(6), 1632–1639.
   Web of Science ®Google Scholar
• Cai, S. (2015). Balance between complexity and quality: Local search for minimum vertex cover in massive graphs. In 24th International Joint Conference on Artificial Intelligence.
   Google Scholar
• Cai, S., Lin, J., & Su, K. (2015). Two weighting local search for minimum vertex cover. In 29th Aaai Conference on Artificial Intelligence.
   Google Scholar
• Cai, S., Su, K., & Chen, Q. (2010). Ewls: A new local search for minimum vertex cover. In 24th Aaai Conference on Artificial Intelligence.
   Google Scholar
• Cai, S., Lin, J., & Luo, C. (2017). Finding a small vertex cover in massive sparse graphs: Construct, local search, and preprocess. Journal of Artificial Intelligence Research, 59, 463–494.
   Web of Science ®Google Scholar
• Cai, S., Su, K., Luo, C., & Sattar, A. (2013). Numvc: An efficient local search algorithm for minimum vertex cover. Journal of Artificial Intelligence Research, 46, 687–716.
   Web of Science ®Google Scholar
• Cai, S., Su, K., & Sattar, A. (2011). Local search with edge weighting and configuration checking heuristics for minimum vertex cover. Artificial Intelligence, 175(9–10), 1672–1696.
   Web of Science ®Google Scholar
• Chandu, D. P. (2014). A parallel genetic algorithm for generalized vertex cover problem. arXiv preprint arXiv:1411.7612
   Google Scholar
• Evans, I. (1998). An evolutionary heuristic for the minimum vertex cover problem. In Proceedings of the Seventh International Conference on Evolutionary Programming (ep) (pp. 377–386).
   Google Scholar
• Hassin, R., & Levin, A. (2006). The minimum generalized vertex cover problem. ACM Transactions on Algorithms (TALG), 2(1), 66–78.
   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.
   Web of Science ®Google Scholar
• Jovanovic, R., & Tuba, M. (2011). An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem. Applied Soft Computing, 11(8), 5360–5366.
   Web of Science ®Google Scholar
• Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations (pp. 85–103). Springer.
   Google Scholar
• Kochenberger, G., Lewis, M., Glover, F., & Wang, H. (2015). Exact solutions to generalized vertex covering problems: A comparison of two models. Optimization Letters, 9(7), 1331–1339.
   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 and Applications, 28(1), 1059–1067.
   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.
   Web of Science ®Google Scholar
• Luo, C., Hoos, H. H., Cai, S., Lin, Q., Zhang, H., & Zhang, D. (2019). Local search with efficient automatic configuration for minimum vertex cover. In IJCAI (pp. 1297–1304).
   Google Scholar
• Luo, W., Ye, R., Wan, H., Cai, S., Fang, B., & Zhang, D. (2022). Improving local search algorithms via probabilistic configuration checking. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022 (pp. 10283–10290). AAAI Press.
   Google Scholar
• Milanovic, M. (2010). Solving the generalized vertex cover problem by genetic algorithm. Computing and Informatics, 29(6), 1251–1265.
   Web of Science ®Google Scholar
• Pullan, W., & Hoos, H. H. (2006). Dynamic local search for the maximum clique problem. Journal of Artificial Intelligence Research, 25, 159–185.
   Web of Science ®Google Scholar
• Richter, S., Helmert, M., Gretton, C. (2007). A stochastic local search approach to vertex cover. In Annual Conference on Artificial Intelligence (pp. 412–426).
   Google Scholar
• Wang, G., Guo, L., Wang, H., Duan, H., Liu, L., & Li, J. (2014). Incorporating mutation scheme into krill herd algorithm for global numerical optimization. Neural Computing and Applications, 24(3), 853–871.
   Web of Science ®Google Scholar
• Wang, G.-G., Gandomi, A. H., & Alavi, A. H. (2014). Stud krill herd algorithm. Neurocomputing, 128, 363–370.
   Web of Science ®Google Scholar
• Wang, Y., Cai, S., Chen, J., & Yin, M. (2020). Sccwalk: An efficient local search algorithm and its improvements for maximum weight clique problem. Artificial Intelligence, 280, 103230.
   Web of Science ®Google Scholar
• Wang, Y., Cai, S., Pan, S., Li, X., Yin, M. (2020). Reduction and local search for weighted graph coloring problem. In Proceedings of the Aaai Conference on Artificial Intelligence (Vol. 34, pp. 2433–2441).
   Google Scholar
• Wang, Y., Li, R., Zhou, Y., & Yin, M. (2017). A path cost-based grasp for minimum independent dominating set problem. Neural Computing and Applications, 28(1), 143–151.
   Google Scholar
• Wang, Y., Ouyang, D., Zhang, L., & Yin, M. (2017). A novel local search for unicost set covering problem using hyperedge configuration checking and weight diversity. Science China Information Sciences, 60(6), 062103.
   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.
   Web of Science ®Google Scholar
• Zhang, X., Li, B., Cai, S., & Wang, Y. (2021). Efficient local search based on dynamic connectivity maintenance for minimum connected dominating set. Journal of Artificial Intelligence Research, 71, 89–119.
   Google Scholar
• Zhou, T., Lü, Z., Wang, Y., Ding, J., & Peng, B. (2016). Multi-start iterated tabu search for the minimum weight vertex cover problem. Journal of Combinatorial Optimization, 32(2), 368–384.
   Web of Science ®Google Scholar
• Zhou, Y., Liu, X., Hu, S., Wang, Y., & Yin, M. (2022). Combining max–min ant system with effective local search for solving the maximum set k-covering problem. Knowledge-Based Systems, 239, 108000.
   Web of Science ®Google Scholar