NuMWVC: A novel local search for minimum weighted vertex cover problem

References

• Akiba, T., & Iwata, Y. (2016). Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover. Theoretical Computer Science, 609, 211–225. doi:10.1016/j.tcs.2015.09.023
   Web of Science ®Google Scholar
• Balachandar, S. R., & Kannan, K. (2009). A meta-heuristic algorithm for vertex covering problem based on gravity. International Journal of Mathematical and Statistical Sciences, 1(3), 130–136.
   Google Scholar
• Balaji, S., Swaminathan, V., & Kannan, K. (2010). An effective algorithm for minimum weighted vertex cover problem. International Journal of Computational and Mathematical Sciences, 4, 34–38.
   Google Scholar
• Barth, L., Niedermann, B., Nöllenburg, M., & Strash, D. (2016). Temporal map labeling: A new unified framework with experiments. In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (p. 23).
   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. doi:10.1016/j.asoc.2012.02.013
   Web of Science ®Google Scholar
• Cai, S. (2015). Balance between complexity and quality: Local search for minimum vertex cover in massive graphs. In Proceedings of the twenty-fourth international joint conference on artificial intelligence, IJCAI (pp. 25–31).
   Google Scholar
• Cai, S., Lin, J., & Su, K. (2015). Two weighting local search for minimum vertex cover. In Twenty-ninth AAAI conference on artificial intelligence.
   Google Scholar
• Cai, S., & Su, K. (2012). Configuration checking with aspiration in local search for sat. In AAAI.
   Google Scholar
• Cai, S., & Su, K. (2013). Local search for Boolean satisfiability with configuration checking and subscore. Artificial Intelligence, 204, 75–98. doi:10.1016/j.artint.2013.09.001
   Web of Science ®Google Scholar
• Cai, S., Su, K., & Chen, Q. (2010). EWLS: A new local search for minimum vertex cover. In AAAI.
   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. doi:10.1613/jair.3907
   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. doi:10.1016/j.artint.2011.03.003
   Web of Science ®Google Scholar
• Chen, J., Kanj, I. A., & Jia, W. (2001). Vertex cover: Further observations and further improvements. Journal of Algorithms, 41(2), 280–301. doi:10.1006/jagm.2001.1186
   Web of Science ®Google Scholar
• Chen, J., Kanj, I. A., & Xia, G. (2006). Improved parameterized upper bounds for vertex cover. In International symposium on mathematical foundations of computer science (pp. 238–249).
   Google Scholar
• Chen, J., Kanj, I. A., & Xia, G. (2010). Improved upper bounds for vertex cover. Theoretical Computer Science, 411(40–42), 3736–3756. doi:10.1016/j.tcs.2010.06.026
   Web of Science ®Google Scholar
• Dahlum, J., Lamm, S., Sanders, P., Schulz, C., Strash, D., & Werneck, R. F. (2016). Accelerating local search for the maximum independent set problem. In International symposium on experimental algorithms (pp. 118–133).
   Google Scholar
• Dinur, I., & Safra, S. (2005). On the hardness of approximating minimum vertex cover. Annals of Mathematics, 162(1), 439–485. doi:10.4007/annals.2005.162.439
   Web of Science ®Google Scholar
• Fan, Y., Li, C., Ma, Z., Brankovic, L., Estivill-Castro, V., & Sattar, A. (2015). Exploiting reduction rules and data structures: Local search for minimum vertex cover in massive graphs. arXiv Preprint arXiv:1509.05870.
   Google Scholar
• Fang, Z., Li, C.-M., Qiao, K., Feng, X., & Xu, K. (2014). Solving maximum weight clique using maximum satisfiability reasoning. In ECAI (pp. 303–308).
   Google Scholar
• Johnson, D. S., & Trick, M. A. (1996). Cliques, coloring, and satisfiability: Second DIMACS implementation challenge, October 11–13, 1993 (Vol. 26). American Mathematical Soc.
   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. doi:10.1016/j.asoc.2011.05.023
   Web of Science ®Google Scholar
• Karp, R. (1972). Reducibility among combinatorial problems. In R.E. Miller & J.M. Thatcher (Eds.), Complexity of computer computations (pp. 85–103). Plenum Press.
   Google Scholar
• Khuri, S., & Bäck, T. (1994). An evolutionary heuristic for the minimum vertex cover problem. Genetic Algorithms Within the Framework of Evolutionary Computation, 86–90.
   Google Scholar
• Li, C.-M., Jiang, H., & Xu, R.-C. (2015). Incremental MaxSAT reasoning to reduce branches in a branch-and-bound algorithm for MaxClique. In Learning and intelligent optimization (pp. 268–274). Springer.
   Google Scholar
• Li, R., Cai, S., Hu, S., Yin, M., & Gao, J. (2018). NuMWVC: A novel local search for minimum weighted vertex cover problem. In AAAI.
   Google Scholar
• Li, R., Hu, S., Zhang, H., & Yin, M. (2016). An efficient local search framework for the minimum weighted vertex cover problem. Information Sciences, 372, 428–445. doi:10.1016/j.ins.2016.08.053
   Web of Science ®Google Scholar
• Li, Y., Cai, S., & Hou, W. (2017). An efficient local search algorithm for minimum weighted vertex cover on massive graphs. In Asia-Pacific Conference on Simulated Evolution and Learning (pp. 145–157).
   Google Scholar
• Luo, C., Cai, S., Su, K., & Wu, W. (2015). Clause states-based configuration checking in local search for satisfiability. IEEE Transactions on Cybernetics, 45(5), 1014–1027. doi:10.1109/TCYB.2014.2343242
   Web of Science ®Google Scholar
• Luo, C., Cai, S., Wu, W., Jie, Z., & Su, K.-W. (2014). CCLS: An efficient local search algorithm for weighted maximum satisfiability. IEEE Transactions on Computers, 64(7), 1830–1843. doi:10.1109/TC.2014.2346196
   Web of Science ®Google Scholar
• Niedermeier, R., & Rossmanith, P. (2003). On efficient fixed-parameter algorithms for weighted vertex cover. Journal of Algorithms, 47(2), 63–77. doi:10.1016/S0196-6774(03)00005-1
   Web of Science ®Google Scholar
• Richter, S., Helmert, M., & Gretton, C. (2007). A stochastic local search approach to vertex cover. In KI 2007: Advances in artificial intelligence (pp. 412–426). Springer.
   Google Scholar
• Rossi, R. A., & Ahmed, N. K. (2015). The network data repository with interactive graph analytics and visualization. In Proceedings of the twenty-ninth AAAI conference on artificial intelligence.
   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. doi:10.1023/B:ANOR.0000039523.95673.33
   Web of Science ®Google Scholar
• Verma, A., Buchanan, A., & Butenko, S. (2015). Solving the maximum clique and vertex coloring problems on very large sparse networks. INFORMS Journal on Computing, 27(1), 164–177. doi:10.1287/ijoc.2014.0618
   Web of Science ®Google Scholar
• Voß, S., & Fink, A. (2012). A hybridized tabu search approach for the minimum weight vertex cover problem. Journal of Heuristics, 18(6), 869–876. doi:10.1007/s10732-012-9211-9
   Web of Science ®Google Scholar
• Wang, Y., Cai, S., & Yin, M. (2016). Two efficient local search algorithms for maximum weight clique problem. In AAAI 2016. doi:10.1007/s11432-015-5377-8
   Google Scholar
• Wang, Y., Cai, S., & Yin, M. (2017). Local search for minimum weight dominating set with two-level configuration checking and frequency based scoring function. In Twenty-Sixth International Joint Conference on Artificial Intelligence (Vol. 58, pp. 267–295). doi:10.1613/jair.5205
   Google Scholar
• Wang, Y., Ouyang, D., Zhang, L., & Yin, M. (2015). A novel local search for unicost set covering problem using hyperedge configuration checking and weight diversity. Science China Information Sciences, 60, 062103
   Web of Science ®Google Scholar
• Xie, X., Qin, X., Yu, C., & Xu, X. (2017). Test-cost-sensitive rough set based approach for minimum weight vertex cover problem. Applied Soft Computing, 64, 423–435. doi:10.1016/j.asoc.2017.12.023
   Web of Science ®Google Scholar
• Xu, K., Boussemart, F., Hemery, F., & Lecoutre, C. (2007). Random constraint satisfaction: Easy generation of hard (satisfiable) instances. Artificial Intelligence, 171(8–9), 514–534. doi:10.1016/j.artint.2007.04.001
   Web of Science ®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. doi:10.1007/s10878-015-9909-3
   Web of Science ®Google Scholar