{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T16:38:17Z","timestamp":1769013497620,"version":"3.49.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T00:00:00Z","timestamp":1768953600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T00:00:00Z","timestamp":1768953600000},"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":["Front. Comput. Sci."],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1007\/s11704-024-40814-y","type":"journal-article","created":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T01:01:45Z","timestamp":1768957305000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An exact algorithm with a new upper bound and reductions for maximum edge weighted clique in massive sparse graphs"],"prefix":"10.1007","volume":"20","author":[{"given":"Shuli","family":"Hu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiaqi","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wen","family":"Wen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yupeng","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruizhi","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minghao","family":"Yin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,21]]},"reference":[{"issue":"7043","key":"40814_CR1","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1038\/nature03607","volume":"435","author":"G Palla","year":"2005","unstructured":"Palla G, Der\u00e9nyi I, Farkas I, Vicsek T. Uncovering the overlapping community structure of complex networks in nature and society. Nature, 2005, 435(7043): 814\u2013818","journal-title":"Nature"},{"issue":"7028","key":"40814_CR2","doi-asserted-by":"publisher","first-page":"895","DOI":"10.1038\/nature03288","volume":"433","author":"R Guimer\u00e0","year":"2005","unstructured":"Guimer\u00e0 R, Nunes Amaral L A. Functional cartography of complex metabolic networks. Nature, 2005, 433(7028): 895\u2013900","journal-title":"Nature"},{"key":"40814_CR3","first-page":"670","volume-title":"Proceedings of 2012 IEEE Conference on Computer Vision and Pattern Recognition","author":"T Ma","year":"2012","unstructured":"Ma T, Jan Latecki L. Maximum weight cliques with mutex constraints for video object segmentation. In: Proceedings of 2012 IEEE Conference on Computer Vision and Pattern Recognition. 2012, 670\u2013677"},{"key":"40814_CR4","first-page":"485","volume-title":"Proceedings of the 4th International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition","author":"M Pavan","year":"2003","unstructured":"Pavan M, Pelillo M. Generalizing the Motzkin-Straus theorem to edge-weighted graphs, with applications to image segmentation. In: Proceedings of the 4th International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition. 2003, 485\u2013500"},{"issue":"1","key":"40814_CR5","first-page":"3","volume":"17","author":"J B Brown","year":"2006","unstructured":"Brown J B, Dukka Bahadur K C, Tomita E, Akutsu T. Multiple methods for protein side chain packing using maximum weight cliques. Genome Informatics, 2006, 17(1): 3\u201312","journal-title":"Genome Informatics"},{"issue":"1","key":"40814_CR6","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0377-2217(93)90097-7","volume":"69","author":"G Dijkhuizen","year":"1993","unstructured":"Dijkhuizen G, Faigle U. A cutting-plane approach to the edge-weighted maximal clique problem. European Journal of Operational Research, 1993, 69(1): 121\u2013130","journal-title":"European Journal of Operational Research"},{"issue":"6","key":"40814_CR7","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1016\/j.jretconser.2007.02.003","volume":"14","author":"L Cavique","year":"2007","unstructured":"Cavique L. A scalable algorithm for the market basket analysis. Journal of Retailing and Consumer Services, 2007, 14(6): 400\u2013407","journal-title":"Journal of Retailing and Consumer Services"},{"issue":"2","key":"40814_CR8","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s10732-007-9026-2","volume":"14","author":"W Pullan","year":"2008","unstructured":"Pullan W. Approximating the maximum vertex\/edge weighted clique using local search. Journal of Heuristics, 2008, 14(2): 117\u2013134","journal-title":"Journal of Heuristics"},{"issue":"3","key":"40814_CR9","first-page":"260","volume":"11","author":"D B M M Fontes","year":"2018","unstructured":"Fontes D B M M, Goncalves J F, Fontes F A C C. An evolutionary approach to the maximum edge weight clique problem. Recent Advances in Electrical & Electronic Engineering, 2018, 11(3): 260\u2013266","journal-title":"Recent Advances in Electrical & Electronic Engineering"},{"key":"40814_CR10","doi-asserted-by":"publisher","first-page":"10743","DOI":"10.1109\/ACCESS.2018.2799953","volume":"6","author":"R Li","year":"2018","unstructured":"Li R, Wu X, Liu H, Wu J, Yin M. An efficient local search for the maximum edge weighted clique problem. IEEE Access, 2018, 6: 10743\u201310753","journal-title":"IEEE Access"},{"issue":"4","key":"40814_CR11","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1007\/s10878-020-00529-9","volume":"39","author":"Y Chu","year":"2020","unstructured":"Chu Y, Liu B, Cai S, Luo C, You H. An efficient local search algorithm for solving maximum edge weight clique problem in large graphs. Journal of Combinatorial Optimization, 2020, 39(4): 933\u2013954","journal-title":"Journal of Combinatorial Optimization"},{"key":"40814_CR12","first-page":"568","volume-title":"Proceedings of the 25th International Joint Conference on Artificial Intelligence","author":"S Cai","year":"2016","unstructured":"Cai S, Lin J. Fast solving maximum weight clique problem in massive graphs. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence. 2016, 568\u2013574"},{"key":"40814_CR13","first-page":"830","volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence","author":"H Jiang","year":"2017","unstructured":"Jiang H, Li C-M, Manya F. An exact algorithm for the maximum weight clique problem in large graphs. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence. 2017, 830\u2013838"},{"issue":"1","key":"40814_CR14","doi-asserted-by":"publisher","first-page":"171406","DOI":"10.1007\/s11704-022-2178-2","volume":"17","author":"C Xiong","year":"2023","unstructured":"Xiong C, Liu H, Wu X, Deng N. A two-level meta-heuristic approach for the minimum dominating tree problem. Frontiers of Computer Science, 2023, 17(1): 171406","journal-title":"Frontiers of Computer Science"},{"issue":"4","key":"40814_CR15","doi-asserted-by":"publisher","first-page":"174326","DOI":"10.1007\/s11704-022-2023-7","volume":"17","author":"S Pan","year":"2023","unstructured":"Pan S, Ma Y, Wang Y, Zhou Z, Ji J, Yin M, Hu S. An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem. Frontiers of Computer Science, 2023, 17(4): 174326","journal-title":"Frontiers of Computer Science"},{"issue":"12","key":"40814_CR16","doi-asserted-by":"publisher","first-page":"8753","DOI":"10.1007\/s10489-021-02305-6","volume":"51","author":"S Hu","year":"2021","unstructured":"Hu S, Liu H, Wang Y, Li R, Yin M, Yang N. Towards efficient local search for the minimum total dominating set problem. Applied Intelligence, 2021, 51(12): 8753\u20138767","journal-title":"Applied Intelligence"},{"issue":"1","key":"40814_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s13675-014-0028-1","volume":"3","author":"L Gouveia","year":"2015","unstructured":"Gouveia L, Martins P. Solving the maximum edge-weight clique problem in sparse graphs with compact formulations. EURO Journal on Computational Optimization, 2015, 3(1): 1\u201330","journal-title":"EURO Journal on Computational Optimization"},{"key":"40814_CR18","first-page":"313","volume":"100","author":"S Shimizu","year":"2017","unstructured":"Shimizu S, Yamaguchi K, Masuda S. Mathematical programming formulation for the maximum edge-weight clique problem. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (in Japanese), 2017, 100: 313\u2013315","journal-title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"},{"issue":"2","key":"40814_CR19","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s10898-018-0630-5","volume":"72","author":"S Hosseinian","year":"2018","unstructured":"Hosseinian S, Fontes D B, Butenko S. A nonconvex quadratic optimization approach to the maximum edge weight clique problem. Journal of Global Optimization, 2018, 72(2): 219\u2013240","journal-title":"Journal of Global Optimization"},{"key":"40814_CR20","first-page":"27","volume-title":"Computational Science\/Intelligence & Applied Informatics","author":"S Shimizu","year":"2018","unstructured":"Shimizu S, Yamaguchi K, Masuda S. A branch-and-bound based exact algorithm for the maximum edge-weight clique problem. In Lee R, ed. Computational Science\/Intelligence & Applied Informatics. Cham: Springer, 2018, 27\u201347"},{"issue":"1","key":"40814_CR21","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.ejor.2019.03.047","volume":"278","author":"P San Segundo","year":"2019","unstructured":"San Segundo P, Coniglio S, Furini F, Ljubi\u0107 I. A new branch-and-bound algorithm for the maximum edge-weighted clique problem. European Journal of Operational Research, 2019, 278(1): 76\u201390","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"40814_CR22","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1287\/ijoc.2019.0898","volume":"32","author":"S Hosseinian","year":"2020","unstructured":"Hosseinian S, Fontes D B M M, Butenko S. A lagrangian bound on the clique number and an exact algorithm for the maximum edge weight clique problem. INFORMS Journal on Computing, 2020, 32(3): 747\u2013762","journal-title":"INFORMS Journal on Computing"},{"key":"40814_CR23","doi-asserted-by":"publisher","first-page":"100583","DOI":"10.1016\/j.disopt.2020.100583","volume":"37","author":"S Shimizu","year":"2020","unstructured":"Shimizu S, Yamaguchi K, Masuda S. A maximum edge-weight clique extraction algorithm based on branch-and-bound. Discrete Optimization, 2020, 37: 100583","journal-title":"Discrete Optimization"},{"key":"40814_CR24","first-page":"20768","volume-title":"Proceedings of the 38th AAAI Conference on Artificial Intelligence","author":"L Liu","year":"2024","unstructured":"Liu L, Xiao M, Zhou Y. A fast exact solver with theoretical analysis for the maximum edge-weighted clique problem. In: Proceedings of the 38th AAAI Conference on Artificial Intelligence. 2024, 20768\u201320776"},{"key":"40814_CR25","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/j.dam.2020.02.003","volume":"296","author":"F Marinelli","year":"2021","unstructured":"Marinelli F, Pizzuti A, Rossi F. LP-based dual bounds for the maximum quasi-clique problem. Discrete Applied Mathematics, 2021, 296: 118\u2013140","journal-title":"Discrete Applied Mathematics"},{"key":"40814_CR26","doi-asserted-by":"publisher","first-page":"105131","DOI":"10.1016\/j.cor.2020.105131","volume":"127","author":"X Chen","year":"2021","unstructured":"Chen X, Zhou Y, Hao J-K, Xiao M. Computing maximum k-defective cliques in massive graphs. Computers & Operations Research, 2021, 127: 105131","journal-title":"Computers & Operations Research"},{"issue":"1","key":"40814_CR27","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/s13278-014-0228-y","volume":"4","author":"R A Rossi","year":"2014","unstructured":"Rossi R A, Ahmed N K. Coloring large complex networks. Social Network Analysis and Mining, 2014, 4(1): 228","journal-title":"Social Network Analysis and Mining"},{"key":"40814_CR28","first-page":"517","volume-title":"Proceedings of the 26th International Joint Conference on Artificial Intelligence","author":"J Lin","year":"2017","unstructured":"Lin J, Cai S, Luo C, Su K. A reduction based method for coloring very large graphs. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence. 2017, 517\u2013523"},{"key":"40814_CR29","first-page":"1689","volume-title":"Proceedings of the 30th International Joint Conference on Artificial Intelligence","author":"H Jiang","year":"2021","unstructured":"Jiang H, Zhu D, Xie Z, Yao S, Fu Z-H. A new upper bound based on vertex partitioning for the maximum K-plex problem. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence. 2021, 1689\u20131696"}],"container-title":["Frontiers of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-024-40814-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11704-024-40814-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-024-40814-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T01:01:47Z","timestamp":1768957307000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11704-024-40814-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,21]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["40814"],"URL":"https:\/\/doi.org\/10.1007\/s11704-024-40814-y","relation":{},"ISSN":["2095-2228","2095-2236"],"issn-type":[{"value":"2095-2228","type":"print"},{"value":"2095-2236","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,21]]},"assertion":[{"value":"5 August 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 November 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests or financial conflicts to disclose.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"2006402"}}