{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T23:50:28Z","timestamp":1762300228747,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2022,12,3]],"date-time":"2022-12-03T00:00:00Z","timestamp":1670025600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,3]],"date-time":"2022-12-03T00:00:00Z","timestamp":1670025600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100011033","name":"Agencia Estatal de Investigaci\u00f3n","doi-asserted-by":"publisher","award":["PID2019-104263RB-C44 and PDC2021-121021-C22"],"award-info":[{"award-number":["PID2019-104263RB-C44 and PDC2021-121021-C22"]}],"id":[{"id":"10.13039\/501100011033","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008431","name":"Consejer\u00eda de Educaci\u00f3n, Junta de Castilla y Le\u00f3n","doi-asserted-by":"publisher","award":["BU056P20"],"award-info":[{"award-number":["BU056P20"]}],"id":[{"id":"10.13039\/501100008431","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Intell"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given an undirected graph, a clique is a subset of vertices in which the induced subgraph is complete; that is, all pairs of vertices of this subset are adjacent. Clique problems in graphs are very important due to their numerous applications. One of these problems is the <jats:italic>clique partitioning problem<\/jats:italic> (CPP), which consists of dividing the set of vertices of a graph into the smallest number of cliques possible. The CPP is an NP-hard problem with many application fields (timetabling, manufacturing, scheduling, telecommunications, etc.). Despite its great applicability, few recent studies have focused on proposing specific resolution methods for the CPP. This article presents a resolution method that combines multistart strategies with tabu search. The most novel characteristic of our method is that it allows unfeasible solutions to be visited, which facilitates exploration of the solution space. The computational tests show that our method performs better than previous methods proposed for this problem. In fact, our method strictly improves the results of these methods in most of the instances considered while requiring less computation time.<\/jats:p>","DOI":"10.1007\/s10489-022-04304-7","type":"journal-article","created":{"date-parts":[[2022,12,3]],"date-time":"2022-12-03T10:02:41Z","timestamp":1670061761000},"page":"16275-16292","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A stepped tabu search method for the clique partitioning problem"],"prefix":"10.1007","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7462-8680","authenticated-orcid":false,"given":"Joaqu\u00edn A.","family":"Pacheco","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Silvia","family":"Casado","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,3]]},"reference":[{"key":"4304_CR1","unstructured":"Allignol C, Barnier N, Gondran A (2012) Optimized flight level allocation at the continental scale. In: 5th international conference for research in air transportation, May 2012, Berkeley"},{"issue":"6","key":"4304_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0898-1221(91)90001-K","volume":"22","author":"J Bhasker","year":"1991","unstructured":"Bhasker J, Samad T (1991) The clique-partitioning problem. Comput Math Appl 22(6):1\u201311","journal-title":"Comput Math Appl"},{"issue":"18","key":"4304_CR3","doi-asserted-by":"publisher","first-page":"3251","DOI":"10.1103\/PhysRevLett.76.3251","volume":"76","author":"M Blatt","year":"1996","unstructured":"Blatt M, Wiseman S, Domany E (1996) Superparamagnetic clustering of data. Phys Rev Lett 76(18):3251\u20133254","journal-title":"Phys Rev Lett"},{"issue":"1","key":"4304_CR4","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/j.ejor.2020.03.010","volume":"286","author":"S Casado","year":"2020","unstructured":"Casado S, Laguna M, Pacheco J, Puche JC (2020) Grouping products for the optimization of production processes: a case in the steel manufacturing industry. Eur J Oper Res 286(1):190\u2013202","journal-title":"Eur J Oper Res"},{"key":"4304_CR5","doi-asserted-by":"crossref","unstructured":"Chen Z, Yuan L, Lin X, Qin L, Yang J (2020) Efficient maximal balanced clique enumeration in signed networks. In:\u00a0Proceedings of The Web Conference 2020, pp 339\u2013349","DOI":"10.1145\/3366423.3380119"},{"issue":"3","key":"4304_CR6","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1287\/trsc.1070.0211","volume":"42","author":"U Dorndorf","year":"2008","unstructured":"Dorndorf U, Jaehn F, Pesch E (2008) Modelling robust flight-gate scheduling as a clique partitioning problem. Transp Sci 42(3):292\u2013301","journal-title":"Transp Sci"},{"key":"4304_CR7","doi-asserted-by":"crossref","unstructured":"Glover F, Laguna M (1997) Tabu Search. Kluwer Academic Press, London","DOI":"10.1007\/978-1-4615-6089-0"},{"issue":"10","key":"4304_CR8","doi-asserted-by":"publisher","first-page":"4929","DOI":"10.1007\/s00521-020-05289-5","volume":"33","author":"S Hu","year":"2021","unstructured":"Hu S, Wu X, Liu H, Li R, Yin M (2021) A novel two-model local search algorithm with a self-adaptive parameter for clique partitioning problem. Neural Comput & Applic 33(10):4929\u20134944","journal-title":"Neural Comput & Applic"},{"issue":"5","key":"4304_CR9","doi-asserted-by":"publisher","first-page":"5173","DOI":"10.1007\/s10489-021-02656-0","volume":"52","author":"M Katukuri","year":"2022","unstructured":"Katukuri M, Jagarapu M (2022) CIM: clique-based heuristic for finding influential nodes in multilayer networks. Appl Intell 52(5):5173\u20135184","journal-title":"Appl Intell"},{"key":"4304_CR10","doi-asserted-by":"publisher","first-page":"754","DOI":"10.3938\/jkps.40.754","volume":"40","author":"JT Kim","year":"2002","unstructured":"Kim JT, Shin DR (2002) New efficient clique partitioning algorithms for register-transfer synthesis of data paths. J-Korean Phys Soc 40:754\u2013758","journal-title":"J-Korean Phys Soc"},{"issue":"3","key":"4304_CR11","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1007\/s10878-019-00412-2","volume":"38","author":"Z Liang","year":"2019","unstructured":"Liang Z, Shan E, Kang L (2019) The clique-perfectness and clique-coloring of outer-planar graphs. J Comb Optim 38(3):794\u2013807","journal-title":"J Comb Optim"},{"issue":"9","key":"4304_CR12","doi-asserted-by":"publisher","first-page":"9391","DOI":"10.1109\/TCYB.2021.3051243","volume":"52","author":"Z L\u00fc","year":"2022","unstructured":"L\u00fc Z, Zhou Y, Hao JK (2022) A hybrid evolutionary algorithm for the clique partitioning problem. IEEE Trans Cybern 52(9):9391\u20139403","journal-title":"IEEE Trans Cybern"},{"key":"4304_CR13","first-page":"1356","volume":"2","author":"E Ozcan","year":"2005","unstructured":"Ozcan E, Ersoy E (2005) Final exam scheduler-FES. In 2005 IEEE congress on. Evol Comput 2:1356\u20131363","journal-title":"Evol Comput"},{"issue":"3","key":"4304_CR14","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1145\/348019.348570","volume":"5","author":"PR Panda","year":"2000","unstructured":"Panda PR, Dutt ND, Nicolau A (2000) On-chip vs. off-chip memory: the data partitioning problem in embedded processor-based systems. ACM Trans Des Autom Electron Syst (TODAES) 5(3):682\u2013704","journal-title":"ACM Trans Des Autom Electron Syst (TODAES)"},{"issue":"3","key":"4304_CR15","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01098364","volume":"4","author":"PM Pardalos","year":"1994","unstructured":"Pardalos PM, Xue J (1994) The maximum clique problem. J Glob Optim 4(3):301\u2013328","journal-title":"J Glob Optim"},{"issue":"2","key":"4304_CR16","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s10489-015-0646-1","volume":"43","author":"P San Segundo","year":"2015","unstructured":"San Segundo P, Artieda J (2015) A novel clique formulation for the visual feature matching problem. Appl Intell 43(2):325\u2013342","journal-title":"Appl Intell"},{"issue":"3","key":"4304_CR17","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1007\/s10489-016-0796-9","volume":"45","author":"P San Segundo","year":"2016","unstructured":"San Segundo P, Lopez A, Batsyn M, Nikolaev A, Pardalos PM (2016) Improved initial vertex ordering for exact maximum clique search. Appl Intell 45(3):868\u2013880","journal-title":"Appl Intell"},{"key":"4304_CR18","doi-asserted-by":"crossref","unstructured":"Schenker A, Last M, Bunke H, Kandel A (2003) Clustering of web documents using a graph model. In: Web Document Analysis: Challenges and Opportunities, pp 3\u201318","DOI":"10.1142\/9789812775375_0001"},{"issue":"2","key":"4304_CR19","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1007\/s10489-017-0904-5","volume":"47","author":"S Sundar","year":"2017","unstructured":"Sundar S, Singh A (2017) Two grouping-based metaheuristics for clique partitioning problem. Appl Intell 47(2):430\u2013442","journal-title":"Appl Intell"},{"key":"4304_CR20","unstructured":"Terashima-Marin H, Ross P, Valenzuela-Rendon M (1999) Clique-based crossover for solving the timetabling problem with GAs. In:\u00a0Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No.\u00a099TH8406). IEEE, vol 2, pp 1200\u20131206"},{"issue":"3","key":"4304_CR21","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1016\/j.ejor.2014.09.064","volume":"242","author":"Q Wu","year":"2015","unstructured":"Wu Q, Hao JK (2015) A review on algorithms for maximum clique problems. Eur J Oper Res 242(3):693\u2013709","journal-title":"Eur J Oper Res"},{"key":"4304_CR22","doi-asserted-by":"crossref","unstructured":"Xiao, S, Li, W, Yang, L, Wen, Z (2020) Graph-Coloring Based Spectrum Sharing for V2V communication. In 2020 International conference on UK-China emerging technologies (UCET), 1\u20134. IEEE","DOI":"10.1109\/UCET51115.2020.9205455"}],"container-title":["Applied Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10489-022-04304-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10489-022-04304-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10489-022-04304-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T04:13:23Z","timestamp":1685592803000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10489-022-04304-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,3]]},"references-count":22,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["4304"],"URL":"https:\/\/doi.org\/10.1007\/s10489-022-04304-7","relation":{},"ISSN":["0924-669X","1573-7497"],"issn-type":[{"type":"print","value":"0924-669X"},{"type":"electronic","value":"1573-7497"}],"subject":[],"published":{"date-parts":[[2022,12,3]]},"assertion":[{"value":"27 October 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"All authors declare that they have no conflicts of interest.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}