RT info:eu-repo/semantics/article
T1 A stepped tabu search method for the clique partitioning problem
A1 Pacheco Bonrostro, Joaquín
A1 Casado Yusta, Silvia
K1 Clique partitioning problem
K1 Metaheuristics
K1 Tabu search
K1 Multistart methods
K1 Economía
K1 Economy
AB Given an undirected graph, a clique is a subset of vertices in which the induced subgraph is complete; that is, all pairs of verticesof this subset are adjacent. Clique problems in graphs are very important due to their numerous applications. One of theseproblems is the clique partitioning problem (CPP), which consists of dividing the set of vertices of a graph into the smallestnumber 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 resolutionmethods for the CPP. This article presents a resolution method that combines multistart strategies with tabu search. The mostnovel characteristic of our method is that it allows unfeasible solutions to be visited, which facilitates exploration of the solutionspace. 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 computationtime.
PB Springer Nature
SN 0924-669X
YR 2022
FD 2022-12
LK http://hdl.handle.net/10259/7402
UL http://hdl.handle.net/10259/7402
LA eng
NO Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. This work was partially supported by FEDER funds and the Spanish State Research Agency (Projects PID2019-104263RB-C44 and PDC2021–121021-C22); the Regional Government of “Castilla y León”, Spain (Project BU071G19); the Regional Government of “Castilla y León”; and FEDER funds (Project BU056P20).
DS Repositorio Institucional de la Universidad de Burgos
RD 02-may-2024