{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T00:08:48Z","timestamp":1759018128487,"version":"3.44.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2025,9,27]],"date-time":"2025-09-27T00:00:00Z","timestamp":1758931200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,9,27]],"date-time":"2025-09-27T00:00:00Z","timestamp":1758931200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"DOI":"10.1007\/s42979-025-04391-6","type":"journal-article","created":{"date-parts":[[2025,9,27]],"date-time":"2025-09-27T08:02:18Z","timestamp":1758960138000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Particle Swarm Optimization for Finding Maximum Independent Set"],"prefix":"10.1007","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-0730-0130","authenticated-orcid":false,"given":"Ritika","family":"Verma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dharmendra Prasad","family":"Mahato","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,9,27]]},"reference":[{"key":"4391_CR1","doi-asserted-by":"publisher","first-page":"123456","DOI":"10.1109\/ACCESS.2021.3112345","volume":"9","author":"X Wu","year":"2021","unstructured":"Wu X, Yang B, Zhu Z. Applications of independent sets in network science: a survey. IEEE Access. 2021;9:123456\u201375. https:\/\/doi.org\/10.1109\/ACCESS.2021.3112345.","journal-title":"IEEE Access"},{"key":"4391_CR2","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS. Computers and intractability: a guide to the theory of NP-completeness. San Francisco: W. H. Freeman; 1979."},{"issue":"2","key":"4391_CR3","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/s00453-008-9241-y","volume":"56","author":"N Bourgeois","year":"2010","unstructured":"Bourgeois N, Escoffier B, Paschos VT. Efficient algorithms for maximum independent set problems on certain classes of graphs. Algorithmica. 2010;56(2):144\u201372. https:\/\/doi.org\/10.1007\/s00453-008-9241-y.","journal-title":"Algorithmica"},{"issue":"2","key":"4391_CR4","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"R Boppana","year":"1992","unstructured":"Boppana R, Halld\u00f3rsson MM. Approximating maximum independent sets by excluding subgraphs. BIT Numer Math. 1992;32(2):180\u201396. https:\/\/doi.org\/10.1007\/BF01994876.","journal-title":"BIT Numer Math"},{"key":"4391_CR5","doi-asserted-by":"publisher","first-page":"83094","DOI":"10.1109\/ACCESS.2019.2923262","volume":"7","author":"K Hussain","year":"2019","unstructured":"Hussain K, Salleh MN, Cheng S, Shi Y. A survey on metaheuristic optimization algorithms. IEEE Access. 2019;7:83094\u2013131. https:\/\/doi.org\/10.1109\/ACCESS.2019.2923262.","journal-title":"IEEE Access"},{"issue":"1","key":"4391_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/ACCESS.2019.2923262","volume":"1","author":"M Dorigo","year":"2006","unstructured":"Dorigo M, St\u00fctzle T. Ant colony optimization: algorithms and applications. J Comput Intell Res. 2006;1(1):1\u201328. https:\/\/doi.org\/10.1109\/ACCESS.2019.2923262.","journal-title":"J Comput Intell Res"},{"key":"4391_CR7","doi-asserted-by":"publisher","unstructured":"Mirjalili S, Mirjalili SM, Lewis A. Grey wolf optimizer Adv Eng Softw. 2014;69:46\u201361. https:\/\/doi.org\/10.1016\/j.advengsoft.2013.12.007.","DOI":"10.1016\/j.advengsoft.2013.12.007"},{"key":"4391_CR8","doi-asserted-by":"publisher","first-page":"4759","DOI":"10.1007\/s10462-022-10403-2","volume":"56","author":"Z Kamyab","year":"2023","unstructured":"Kamyab Z, Abbasian-Naghneh SR, Sadollah A. Hybrid metaheuristic algorithms: a comprehensive review of recent trends and applications. Artif Intell Rev. 2023;56:4759\u2013802. https:\/\/doi.org\/10.1007\/s10462-022-10403-2.","journal-title":"Artif Intell Rev"},{"key":"4391_CR9","doi-asserted-by":"publisher","first-page":"4104","DOI":"10.1109\/ICSMC.1997.637339","volume":"5","author":"J Kennedy","year":"1997","unstructured":"Kennedy J, Spears WM. Discrete binary version of the particle swarm algorithm. IEEE Int Conf Syst Man Cybernet. 1997;5:4104\u20138. https:\/\/doi.org\/10.1109\/ICSMC.1997.637339. (IEEE).","journal-title":"IEEE Int Conf Syst Man Cybernet"},{"key":"4391_CR10","doi-asserted-by":"publisher","unstructured":"Kennedy J, Eberhart R. Particle swarm optimization. Proceedings of ICNN\u201995 international conference on neural networks. 1995;4:1942\u201319484. https:\/\/doi.org\/10.1109\/ICNN.1995.488968.","DOI":"10.1109\/ICNN.1995.488968"},{"key":"4391_CR11","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/j.patrec.2019.03.007","volume":"123","author":"L Hu","year":"2018","unstructured":"Hu L, Xu Y, Gu S. Binary particle swarm optimization for feature selection: a review. Pattern Recogn Lett. 2018;123:229\u201334. https:\/\/doi.org\/10.1016\/j.patrec.2019.03.007.","journal-title":"Pattern Recogn Lett"},{"key":"4391_CR12","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2022.110006","volume":"135","author":"X Qin","year":"2023","unstructured":"Qin X, Wang Y. Adaptive particle swarm optimization with dynamic parameter adjustment. Appl Soft Comput. 2023;135:110006. https:\/\/doi.org\/10.1016\/j.asoc.2022.110006.","journal-title":"Appl Soft Comput"},{"key":"4391_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2023.111536","volume":"146","author":"Y Zhang","year":"2024","unstructured":"Zhang Y, Li W, Wang Y. Adaptive binary particle swarm optimization for large-scale feature selection. Appl Soft Comput. 2024;146:111536. https:\/\/doi.org\/10.1016\/j.asoc.2023.111536.","journal-title":"Appl Soft Comput"},{"issue":"3","key":"4391_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3571744","volume":"56","author":"Q Yang","year":"2023","unstructured":"Yang Q, Liu J, Li H. A survey on maximum independent set problem: models, algorithms, and applications. ACM Comput Surv. 2023;56(3):1\u201339. https:\/\/doi.org\/10.1145\/3571744.","journal-title":"ACM Comput Surv"},{"key":"4391_CR15","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/026","volume-title":"Cliques, coloring, and satisfiability: second DIMACS implementation challenge, workshop, October 11\u201313, 1993","author":"DJ Johnson","year":"1996","unstructured":"Johnson DJ, Trick MA. Cliques, coloring, and satisfiability: second DIMACS implementation challenge, workshop, October 11\u201313, 1993. USA: American Mathematical Society; 1996."},{"key":"4391_CR16","doi-asserted-by":"publisher","unstructured":"Bader D, Meyerhenke H, Sanders P, Wagner D. Graph partitioning and graph clustering. Proceedings of the 10th dimacs implementation challenge workshop, Atlanta, GA, USA, February 13\u201314, 2012; 2013. https:\/\/doi.org\/10.1090\/conm\/588.","DOI":"10.1090\/conm\/588"},{"key":"4391_CR17","doi-asserted-by":"crossref","unstructured":"Rossi RA, Ahmed NK. The network data repository with interactive graph analytics and visualization. 2015. http:\/\/networkrepository.com.","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"4391_CR18","doi-asserted-by":"crossref","unstructured":"Mahato RV, Prasad D. Enhancing search strategies for maximum independent set with grey wolf optimization-genetic algorithm. In: Proceedings of the 39th IEEE\/ACM international conference on advanced information networking and applications (AINA 2025). Cham: Springer. https:\/\/doi.org\/10.1007\/978-3-031-87769-8_20.","DOI":"10.1007\/978-3-031-87769-8_20"},{"key":"4391_CR19","doi-asserted-by":"publisher","unstructured":"Mahato RV, Prasad D. Finding maximum independent set using particle swarm optimization. In: Proceedings of the 39th international conference on information networking (ICOIN 2025). IEEE. pp. 584\u2013589 https:\/\/doi.org\/10.1109\/ICOIN55682.2025.00090.","DOI":"10.1109\/ICOIN55682.2025.00090"},{"key":"4391_CR20","doi-asserted-by":"publisher","unstructured":"Kennedy J, Eberhart R. Particle swarm optimization. Proceedings of ICNN\u201995 -international conference on neural networks. 1995;4:1942\u201319484. https:\/\/doi.org\/10.1109\/ICNN.1995.488968.","DOI":"10.1109\/ICNN.1995.488968"},{"key":"4391_CR21","doi-asserted-by":"publisher","unstructured":"Oliva D, Ramos\u00a0Michel A, Navarro M, H\u00a0Haro E, Casas A. Particle swarm optimization; 2023. pp. 49\u201371. https:\/\/doi.org\/10.5281\/zenodo.7537827.","DOI":"10.5281\/zenodo.7537827"},{"key":"4391_CR22","doi-asserted-by":"publisher","unstructured":"Laskari EC, Parsopoulos KE, Vrahatis MN. Particle swarm optimization for minimax problems. Proceedings of the 2002 congress on evolutionary computation CEC\u201902 (Cat No02TH8600). 2002;2:1576\u201315812. https:\/\/doi.org\/10.1109\/CEC.2002.1004477.","DOI":"10.1109\/CEC.2002.1004477"},{"issue":"2","key":"4391_CR23","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s00500-016-2474-6","volume":"22","author":"D Wang","year":"2018","unstructured":"Wang D, Tan D, Liu L. Particle swarm optimization algorithm: an overview. Soft Comput. 2018;22(2):387\u2013408. https:\/\/doi.org\/10.1007\/s00500-016-2474-6.","journal-title":"Soft Comput"},{"key":"4391_CR24","doi-asserted-by":"publisher","unstructured":"Mahato RV, Prasad D. Degree-oriented deterministic approach for maximum independent set. In: Proceedings of the 39th IEEE\/ACM international conference on advanced information networking and applications (AINA 2025). Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-031-87769-8_21.","DOI":"10.1007\/978-3-031-87769-8_21"},{"key":"4391_CR25","doi-asserted-by":"publisher","unstructured":"Verma R, Mahato DP. Maximum independent set using hummingbird optimization. In: Proceedings of the international conference on advanced network technologies and intelligent computing (ANTIC-2024). Springer. pp. 258\u2013272.https:\/\/doi.org\/10.1007\/978-981-99-8459-6_20.","DOI":"10.1007\/978-981-99-8459-6_20"},{"key":"4391_CR26","unstructured":"Mahato RV, Prasad D. Finding maximum independent set using aco_ga algorithm. 2025."},{"key":"4391_CR27","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2023.110474","volume":"144","author":"M Silva","year":"2023","unstructured":"Silva M, Contreras-Bolton C, Rey C, Parada V. Automatic generation of a hybrid algorithm for the maximum independent set problem using genetic programming. Appl Soft Comput. 2023;144:110474. https:\/\/doi.org\/10.1016\/j.asoc.2023.110474.","journal-title":"Appl Soft Comput"},{"issue":"3","key":"4391_CR28","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.eij.2019.12.002","volume":"21","author":"T U\u00e7kan","year":"2020","unstructured":"U\u00e7kan T, Karc\u0131 A. Extractive multi-document text summarization based on graph independent sets. Egypt Inf J. 2020;21(3):145\u201357. https:\/\/doi.org\/10.1016\/j.eij.2019.12.002.","journal-title":"Egypt Inf J"},{"key":"4391_CR29","doi-asserted-by":"publisher","unstructured":"Imanaga T, Nakano K, Tao M, Yasudo R, Ito Y, Kawamata Y, Katsuki R, Tabata Y, Yazane T, Hamano K. Efficient gpu implementation for solving the maximum independent set problem. In: 2020 eighth international symposium on computing and networking (CANDAR). 2020. pp. 29\u201338. https:\/\/doi.org\/10.1109\/CANDAR51075.2020.00012.","DOI":"10.1109\/CANDAR51075.2020.00012"},{"key":"4391_CR30","doi-asserted-by":"publisher","unstructured":"Lamm S, Schulz C, Strash D, Williger R, Zhang H. Exactly solving the maximum weight independent set problem on large real-world graphs, pp. 144\u2013158. https:\/\/doi.org\/10.1137\/1.9781611975499.12.","DOI":"10.1137\/1.9781611975499.12"},{"key":"4391_CR31","unstructured":"Ahn S, Seo Y, Shin J. Learning what to defer for maximum independent sets. In: III HD, Singh A (eds.) Proceedings of the 37th international conference on machine learning. Proceedings of machine learning research, PMLR. 2020;119:134\u2013144. https:\/\/proceedings.mlr.press\/v119\/ahn20a.html."},{"key":"4391_CR32","unstructured":"Gao X-Z, Wang Y-J, Zhang P, Liu J-G. Automated discovery of branching rules with optimal complexity for the maximum independent set problem. 2024. arxiv:2412.07685."},{"key":"4391_CR33","unstructured":"Gro\u00dfmann E, Langedal K, Schulz C. A Comprehensive survey of data reduction rules for the maximum weighted independent set problem. 2024. arxiv:2412.09303."},{"key":"4391_CR34","unstructured":"Gro\u00dfmann E, Langedal K, Schulz C. Accelerating reductions using graph neural networks and a new concurrent local search for the maximum weight independent set problem. 2025. arxiv:2412.14198."},{"key":"4391_CR35","doi-asserted-by":"publisher","DOI":"10.1016\/j.jestch.2025.101995","volume":"63","author":"F \u00d6ztemiz","year":"2025","unstructured":"\u00d6ztemiz F. A greedy approach to solve maximum independent set problem: differential Malatya independent set algorithm. Eng Sci Technol Int J. 2025;63:101995. https:\/\/doi.org\/10.1016\/j.jestch.2025.101995.","journal-title":"Eng Sci Technol Int J"},{"issue":"5","key":"4391_CR36","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.110.052435","volume":"110","author":"L Brady","year":"2024","unstructured":"Brady L, Hadfield S. Iterative quantum algorithms for maximum independent set. Phys Rev A. 2024;110(5):052435. https:\/\/doi.org\/10.1103\/PhysRevA.110.052435.","journal-title":"Phys Rev A"},{"key":"4391_CR37","doi-asserted-by":"publisher","unstructured":"Bomze IM, Budinich M, Pardalos PM, Pelillo M. In: Du DZ, Pardalos PM (eds.) The maximum clique problem. Boston: Springer; 1999. pp. 1\u201374. https:\/\/doi.org\/10.1007\/978-1-4757-3023-4_1.","DOI":"10.1007\/978-1-4757-3023-4_1"},{"key":"4391_CR38","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01098364","volume":"4","author":"PM Pardalos","year":"1994","unstructured":"Pardalos PM, Xue J. The maximum clique problem. J Global Optim. 1994;4:301\u201328. https:\/\/doi.org\/10.1007\/BF01098364.","journal-title":"J Global Optim"},{"issue":"1","key":"4391_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lovasz","year":"1979","unstructured":"Lovasz L. On the shannon capacity of a graph. IEEE Trans Inf Theory. 1979;25(1):1\u20137. https:\/\/doi.org\/10.1109\/TIT.1979.1055985.","journal-title":"IEEE Trans Inf Theory"},{"key":"4391_CR40","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF02024498","volume":"10","author":"T Gallai","year":"1959","unstructured":"Gallai T, et al. On maximal paths and circuits of graphs. Acta Math Acad Sci Hungar. 1959;10:337\u201356. https:\/\/doi.org\/10.1007\/BF02024498.","journal-title":"Acta Math Acad Sci Hungar"},{"key":"4391_CR41","doi-asserted-by":"publisher","unstructured":"Kennedy J, Eberhart RC. Swarm Intelligence. San Francisco: Morgan Kaufmann Publishers; 2001. https:\/\/doi.org\/10.1016\/B978-1-55860-595-4.X5000-1.","DOI":"10.1016\/B978-1-55860-595-4.X5000-1"},{"key":"4391_CR42","doi-asserted-by":"publisher","unstructured":"Kennedy J, Eberhart R. Particle swarm optimization. Proceedings of ICNN\u201995 - international conference on neural networks. 1995;4:1942\u201319484. https:\/\/doi.org\/10.1109\/ICNN.1995.488968.","DOI":"10.1109\/ICNN.1995.488968"},{"key":"4391_CR43","doi-asserted-by":"crossref","unstructured":"Rossi RA, Ahmed NK. The network data repository with interactive graph analytics and visualization. In: AAAI. 2015. https:\/\/networkrepository.com.","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"4391_CR44","doi-asserted-by":"publisher","unstructured":"Qin Z, Yu F, Shi Z, Wang Y. Adaptive inertia weight particle swarm optimization. In: Artificial intelligence and soft computing ICAISC 2006. Springer. 2006. pp. 450\u2013459. https:\/\/doi.org\/10.1007\/11785231_48.","DOI":"10.1007\/11785231_48"},{"issue":"5","key":"4391_CR45","doi-asserted-by":"publisher","first-page":"368","DOI":"10.7763\/IJMLC.2015.V5.535","volume":"5","author":"S Kessentini","year":"2015","unstructured":"Kessentini S, Barchiesi D, et al. Particle swarm optimization with adaptive inertia weight. Int J Mach Learn Comput. 2015;5(5):368\u201372.","journal-title":"Int J Mach Learn Comput"},{"key":"4391_CR46","unstructured":"Dru\u0161eta S, Ivic S. Anakatabatic inertia: Particle-wise adaptive inertia for PSO 2020. https:\/\/arxiv.org\/abs\/2008.00979."},{"issue":"9","key":"4391_CR47","doi-asserted-by":"publisher","first-page":"0275094","DOI":"10.1371\/journal.pone.0275094","volume":"17","author":"P Aivaliotis-Apostolopoulos","year":"2022","unstructured":"Aivaliotis-Apostolopoulos P, Loukidis D. Swarming genetic algorithm: a nested fully coupled hybrid of genetic algorithm and particle swarm optimization. PLoS ONE. 2022;17(9):0275094. https:\/\/doi.org\/10.1371\/journal.pone.0275094.","journal-title":"PLoS ONE"},{"key":"4391_CR48","doi-asserted-by":"crossref","unstructured":"Boks R, Wang H, B\u00e4ck T. A modular hybridization of particle swarm optimization and differential evolution 2020. arxiv:2006.11886.","DOI":"10.1145\/3377929.3398123"},{"issue":"1","key":"4391_CR49","doi-asserted-by":"publisher","first-page":"24928","DOI":"10.1038\/s41598-024-76010-y","volume":"14","author":"J Yao","year":"2024","unstructured":"Yao J, Luo X, Li F, Li J, Dou J, Luo H. Research on hybrid strategy particle swarm optimization algorithm and its applications. Sci Rep. 2024;14(1):24928. https:\/\/doi.org\/10.1038\/s41598-024-76010-y.","journal-title":"Sci Rep"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-025-04391-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-025-04391-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-025-04391-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,27]],"date-time":"2025-09-27T20:03:04Z","timestamp":1759003384000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-025-04391-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,27]]},"references-count":49,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2025,10]]}},"alternative-id":["4391"],"URL":"https:\/\/doi.org\/10.1007\/s42979-025-04391-6","relation":{},"ISSN":["2661-8907"],"issn-type":[{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,27]]},"assertion":[{"value":"11 April 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 September 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"858"}}