2026-04-20T02:43:14Zhttps://riubu.ubu.es/oai/request

oai:riubu.ubu.es:10259/74022024-05-10T11:56:11Zcom_10259_5645com_10259_5086com_10259_2604col_10259_5646

Pacheco Bonrostro, Joaquín Casado Yusta, Silvia Clique partitioning problem Metaheuristics Tabu search Multistart methods 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 clique partitioning problem (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. 2023-02-06 2023-02-06 2022-12 info:eu-repo/semantics/article 0924-669X http://hdl.handle.net/10259/7402 10.1007/s10489-022-04304-7 1573-7497 eng Applied Intelligence. 2022 https://doi.org/10.1007/s10489-022-04304-7 info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2019-104263RB-C44/ES/MEJORA EN LA TOMA DE DECISIONES EN EL AMBITO DE LA LOGISTICA Y PROBLEMAS RELACIONADOS. ENFOQUE MULTI-OBJETIVO/ info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PDC2021-121021-C22/ES/Sistemas de apoyo a la toma de decisiones eficientes: Planificación de la logística externa e interna y selección de carteras/ info:eu-repo/grantAgreement/Junta de Castilla y León//BU071G19//Métodos heurísticos para problemas de optimización de recursos sanitarios con varios objetivos/ info:eu-repo/grantAgreement/Junta de Castilla y León//BU056P20//Análisis de problemas de logística sanitaria: Enfoque multi-objetivo y uso de metaheurísticas/ http://creativecommons.org/licenses/by/4.0/ info:eu-repo/semantics/openAccess Atribución 4.0 Internacional Springer Nature