УДК 519.854

П.В. ШИЛО
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
 petershylo@gmail.com

ГІБРИДНИЙ АЛГОРИТМ РОЗВ’ЯЗАННЯ ЗАДАЧІ ЗНАХОДЖЕННЯ
МАКСИМАЛЬНОЇ НЕЗАЛЕЖНОЇ МНОЖИНИ ВЕРШИН ГРАФУ

СПИСОК ЛІТЕРАТУРИ

1. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы решения, исследования. Киев: Наук. думка, 2003. 264 с.
2. Butenko S. Maximum independent set and related problems with applications. PhD thesis, University of Florida, 2003. Р. 155.
3. Zheng M., Hao J.-K., Wu Q. Exact and heuristic solution approaches for the Generalized Independent Set Problem. Computers & Operations Research. 2024. Vol. 164. Article number 106561. https://doi.org/10.1016/j.cor.2024.106561.
4. Glover F. Tabu search (part I). ORSA Journal on Computing. 1989. Vol. 1, N 3. P. 190–206. https://doi.org/10.1287/ijoc.1.3.190.
5. Glover F. Tabu search (part II). ORSA Journal on Computing. 1990. Vol. 2, N 1. P. 4–32. https://doi.org/10.1287/ijoc.2.1.4.
6. Alsheddy A., Voudouris C., Tsang E.P.K., Alhindi A. Guided Local Search. Handbook of Heuristics. Marti R., Pardalos P., Resende M. (Eds.). Cham, Springer, 2018. P. 261–297. https://doi.org/10.1007/978-3-319-07124-4_2.
7. Voudouris C., Tsang E. Guided local search and its application to the traveling salesman problem. European Journal of Operational Research. 1999. Vol. 113, N 2. P. 469–499. https://doi.org/10.1016/S0377-2217(98)00099-X.
8. Glover F., Laguna M., Martн R. Fundamentals of scatter search and path relinking. Control and Cybernetics. 2000. Vol. 29, N 3. P. 653–684.
9. Carraghan R., Pardalos P.M. An exact algorithm for the maximum clique problem. Operations Research Letters. 1990. Vol. 9, N 6. P. 375–382. https://doi.org/10.1016/0167-6377(90)90057-C.
10. San Segundo P., Rodrнguez-Losada D., Jimйnez A. An exact bit-parallel algorithm for the maximum clique problem. Computers & Operations Research. 2011. Vol. 38, N 2. P. 571–581. https://doi.org/10.1016/j.cor.2010.07.019.
11. Grosso A., Locatelli M., Pullan W. Simple ingredients leading to very efficient heuristics for the maximum clique problem. Journal of Heuristics. 2008. Vol. 14, N 6. P. 587–612. https://doi.org/10.1007/s10732-007-9055-x.
12. Katayama K., Hamamoto A., Narihisa H. An effective local search for the maximum clique problem. Information Processing Letters. 2005. Vol. 95, N 5. P. 503–511. https://doi.org/10.1016/j.ipl.2005.05.010.
13. Hansen P., Mladenovi N., Uroevi D. Variable neighborhood search for the maximum clique. Discrete Applied Mathematics. 2004. Vol. 145, N 1. P. 117–125. https://doi.org/10.1016/j.dam.2003.09.012.
14. Brunato M., Battiti R. R-EVO: A reactive evolutionary algorithm for the maximum clique problem. IEEE Transactions on Evolutionary Computation. 2011. Vol. 15, N 6. P. 770–782. https://doi.org/10.1109/TEVC.2010.2043363.
15. Zhang Q., Sun J., Tsang E. An evolutionary algorithm with guided mutation for the maximum clique problem. IEEE Transactions on Evolutionary Computation. 2005. Vol. 9, N 2. P. 192–200. https://doi.org/10.1109/TEVC.2004.840835.
16. Johnson D.S., Trick M.A. (Eds.) Cliques, coloring, and satisfiability: second DIMACS implementation challenge. Providence, American Mathematical Society. 1996. Vol. 26. P. 657. https://doi.org/10.1090/dimacs/026.
17. Andrade D.V., Resende M.G.C., Werneck R.F. Fast local search for the maximum independent set problem. Journal of Heuristics. 2012. Vol. 18, N 4. P. 525–547. https://doi.org/10.1007/s10732-012-9196-4.
18. Benlic U., Hao J.-K. Breakout local search for maximum clique problems. Computers & Operations Research. 2013. Vol. 40, N 1. P. 192–206. https://doi.org/10.1016/j.cor.2012.06.002.
19. Cai S., Su K., Luo C., Sattar A. NuMVC: An efficient local search algorithm for minimum vertex cover. Journal of Artificial Intelligence Research. 2013. Vol. 46. P. 687–716. https://doi.org/10.1613/jair.3907.
20. Pullan W. Phased local search for the maximum clique problem. Journal of Combinatorial Optimization. 2006. Vol. 12, N 3. P. 303–323. https://doi.org/10.1007/s10878-006-9635-y.
21. Pullan W., Mascia F., Brunato M. Cooperating local search for the maximum clique problem. Journal of Heuristics. 2011. Vol. 17, N 2. P. 181–199. https://doi.org/10.1007/s10732-010-9131-5.
22. Richter S., Helmert M., Gretton C. A stochastic local search approach to vertex cover. KI 2007: Advances in Artificial Intelligence. J. Hertzberg, M. Beetz, R. Englert (Eds.). Berlin, Heidelberg, Springer. 2007. P. 412–426. https://doi.org/10.1007/978-3-540-74565-5_31.
23. Wu Q., Hao J.-K., Glover F. Multi-neighborhood tabu search for the maximum weight clique problem. Annals of Operations Research. 2012. Vol. 196, N 1. P. 611–634. https://doi.org/10.1007/s10479-012-1124-3.
24. Wu Q., Hao J.-K. An adaptive multistart tabu search approach to solve the maximum clique problem. Journal of Combinatorial Optimization. 2013. Vol. 26, N 1. P. 86–108. https://doi.org/10.1007/s10878-011-9437-8.
25. Jin Y., Hao J.-K. General swap-based multiple neighborhood tabu search for the maximum independent set problem. Engineering Applications of Artificial Intelligence. 2015. Vol. 37. P. 20–33. https://doi.org/10.1016/j.engappai.2014.08.007.