2026-09-16T12:29:34Zhttps://riubu.ubu.es/oai/requestoai:riubu.ubu.es:10259/74022024-05-10T11:56:11Zcom_10259_5645com_10259_5086com_10259_2604col_10259_5646
Pacheco Bonrostro, Joaquín
410
600
0000-0002-7462-8680
Casado Yusta, Silvia
666
600
0000-0002-9663-1557
2023-02-06T12:39:14Z
2023-02-06T12:39:14Z
2022-12
0924-669X
http://hdl.handle.net/10259/7402
10.1007/s10489-022-04304-7
1573-7497
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.
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).
application/pdf
eng
Springer Nature
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/
Atribución 4.0 Internacional
http://creativecommons.org/licenses/by/4.0/
info:eu-repo/semantics/openAccess
Clique partitioning problem
Metaheuristics
Tabu search
Multistart methods
Economía
Economics
A stepped tabu search method for the clique partitioning problem
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
Applied Intelligence
THUMBNAIL
Pacheco-ain_2022.pdf.jpg
Pacheco-ain_2022.pdf.jpg
IM Thumbnail
image/jpeg
4616
https://riubu.ubu.es/bitstream/10259/7402/4/Pacheco-ain_2022.pdf.jpg
f7ff94cbf0d3d5bfd15273f00e1e138b
MD5
4
LICENSE
license.txt
license.txt
text/plain; charset=utf-8
998
https://riubu.ubu.es/bitstream/10259/7402/3/license.txt
aa90105e1c90a1b4fe810649aa967b7d
MD5
3
CC-LICENSE
license_rdf
license_rdf
application/rdf+xml; charset=utf-8
908
https://riubu.ubu.es/bitstream/10259/7402/2/license_rdf
0175ea4a2d4caec4bbcc37e300941108
MD5
2
ORIGINAL
Pacheco-ain_2022.pdf
Pacheco-ain_2022.pdf
application/pdf
1886330
https://riubu.ubu.es/bitstream/10259/7402/1/Pacheco-ain_2022.pdf
6e83007fe28c8fcc981e4533a76ff34e
MD5
1
10259/7402
oai:riubu.ubu.es:10259/7402
2024-05-10 13:56:11.315
Repositorio Institucional de la Universidad de Burgos
bubrep@ubu.es
RWwgYXV0b3IgY29tbyDDum5pY28gdGl0dWxhciBkZSBsb3MgZGVyZWNob3MgZGUgcHJvcGllZGFkIGludGVsZWN0dWFsIGRlIGxhIG9icmEsIG8gZGlzcG9uaWVuZG8gZGUgbG9zIGRlYmlkb3MgcGVybWlzb3MgZGUgbG9zIG90cm9zIHRpdHVsYXJlcywgc2kgbG9zIGh1YmllcmEsIHkgZW4gdmlydHVkIGRlIGxvcyBkZXJlY2hvcyBxdWUgbGUgY29uZmllcmUgbGEgbGVnaXNsYWNpw7NuIHZpZ2VudGUgc29icmUgcHJvcGllZGFkIGludGVsZWN0dWFsIHkgZGVyZWNob3MgZGUgYXV0b3IsIA0KQVVUT1JJWkEgYSBsYSBVbml2ZXJzaWRhZCBkZSBCdXJnb3MgYSBkaWZ1bmRpciwgZGUgbWFuZXJhIGdyYXR1aXRhLCBlbCBjb250ZW5pZG8gZGUgbG9zIGFyY2hpdm9zIGRpZ2l0YWxlcyBxdWUgY29ycmVzcG9uZGVuIGFsIGRvY3VtZW50byBkZXNjcml0byBhbnRlcmlvcm1lbnRlLCBjb24gY2Fyw6FjdGVyIG5vIGV4Y2x1c2l2byB5IGRlIG1hbmVyYSBww7pibGljYSBlbiBhY2Nlc28gYWJpZXJ0byBhIHRyYXbDqXMgZGUgSW50ZXJuZXQsIHBhcmEgbG8gcXVlIGxhIEJpYmxpb3RlY2EgcHJvY2VkZXLDoSBhIGFyY2hpdmFybG9zIGVuIGVsIFJlcG9zaXRvcmlvIEluc3RpdHVjaW9uYWwuIEFzaW1pc21vIGF1dG9yaXphIGEgbGEgVW5pdmVyc2lkYWQgZGUgQnVyZ29zIGEgcmVhbGl6YXIgbGFzIHRyYW5zZm9ybWFjaW9uZXMgbmVjZXNhcmlhcyBkZSBmb3JtYXRvLCBubyBkZSBjb250ZW5pZG8sIHBhcmEgZ2FyYW50aXphciBsYSBwcmVzZXJ2YWNpw7NuIHkgZWwgYWNjZXNvIGVuIGVsIGZ1dHVyby4NCg0KRWwgYXV0b3IgZGlzcG9uZSwgZW4gdG9kbyBjYXNvLCBkZWwgZGVyZWNobyBhIHJldm9jYXIgZXN0YSBhdXRvcml6YWNpw7NuLg0KDQpMYSBjZXNpw7NuIGRlIGRlcmVjaG9zIGRlIGVzdGEgb2JyYSBzZSBlbmN1ZW50cmEgc3VqZXRhIGEgbGEgbGVnaXNsYWNpw7NuIHZpZ2VudGUgc29icmUgcHJvcGllZGFkIGludGVsZWN0dWFsIHkgZGVyZWNob3MgZGUgYXV0b3I=