{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T07:56:42Z","timestamp":1761897402735,"version":"build-2065373602"},"reference-count":19,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2020,10,4]],"date-time":"2020-10-04T00:00:00Z","timestamp":1601769600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Let G=(V,E) be an undirected graph with vertex set V and edge set E. A clique C of G is a subset of the vertices of V with every pair of vertices of C adjacent. A maximum clique is a clique with the maximum number of vertices. A tabu search algorithm for the maximum clique problem that uses an exact algorithm on subproblems is presented. The exact algorithm uses a graph coloring upper bound for pruning, and the best such algorithm to use in this context is considered. The final tabu search algorithm successfully finds the optimal or best known solution for all standard benchmarks considered. It is compared with a state-of-the-art algorithm that does not use exact search. It is slower to find the known optimal solution for most instances but is faster for five instances and finds a larger clique for two instances.<\/jats:p>","DOI":"10.3390\/a13100253","type":"journal-article","created":{"date-parts":[[2020,10,5]],"date-time":"2020-10-05T08:35:57Z","timestamp":1601886957000},"page":"253","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8128-2067","authenticated-orcid":false,"given":"Derek H.","family":"Smith","sequence":"first","affiliation":[{"name":"School of Computing and Mathematics, University of South Wales, Pontypridd, Cardiff CF37 1DL, UK"}]},{"given":"Roberto","family":"Montemanni","sequence":"additional","affiliation":[{"name":"Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, Via Amendola 2 (Pad. Morselli), 42122 Modena MO, Italy"}]},{"given":"Stephanie","family":"Perkins","sequence":"additional","affiliation":[{"name":"School of Computing and Mathematics, University of South Wales, Pontypridd, Cardiff CF37 1DL, UK"}]}],"member":"1968","published-online":{"date-parts":[[2020,10,4]]},"reference":[{"key":"ref_1","unstructured":"Rocha, \u00c1., Correia, A., Adeli, H., Reis, L., and Mendon\u00e7a Teixeira, M. (2016). Graph Colouring and Branch and Bound Approaches for Permutation Code Algorithms. New Advances in Information Systems and Technologies. Advances in Intelligent Systems and Computing, Springer."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1504\/IJMHEUR.2019.098270","article-title":"Solving the maximum clique problem with a hybrid algorithm","volume":"7","author":"Smith","year":"2019","journal-title":"Int. J. Metaheuristics"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/j.engappai.2014.08.007","article-title":"General swap-based neighborhood tabu search for the maximum independent set problem","volume":"37","author":"Jin","year":"2015","journal-title":"Eng. Appl. Artif. Intel."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1016\/j.ejor.2014.09.064","article-title":"A review on algorithms for maximum clique problems","volume":"242","author":"Wu","year":"2015","journal-title":"Eur. J. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Leese, R., and Hurley, S. (2002). Methods and Algorithms for Radio Channel Assignment, Oxford University Press.","DOI":"10.1093\/oso\/9780198503149.001.0001"},{"key":"ref_6","unstructured":"Sloane, N.J.A. (2020, June 17). Challenge Problems: Independent Sets in Graphs. Available online: http:\/\/oeis.org\/A265032\/a265032.html."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/s10623-011-9551-8","article-title":"A new table of permutation codes","volume":"63","author":"Smith","year":"2012","journal-title":"Design. Code. Cryptogr."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Miller, R.E., and Thatcher, J.W. (1972). Reducibility among combinatorial problems. Complexity of Computer Computations, Plenum Press.","DOI":"10.1007\/978-1-4684-2001-2"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Grandinetti, L., Mirtaheri, S., and Shahbazian, R. (2019). A parallel hybrid genetic algorithm for solving the maximum clique problem. High-Performance Computing and Big Data Analysis. TopHPC 2019, Springer.","DOI":"10.1007\/978-3-030-33495-6"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Guo, P., Wang, X., Zeng, Y., and Chen, H. (2019). MEAMCP: A membrane evolutionary algorithm for solving maximum clique problem. IEEE Access, Available online: https:\/\/ieeexplore.ieee.org\/stamp\/stamp.jsp?arnumber=8788505.","DOI":"10.1109\/ACCESS.2019.2933383"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"21","DOI":"10.4018\/IJORIS.2018100102","article-title":"Solving the maximum clique problem using a hybrid particle swarm optimization algorithm","volume":"9","author":"Tayachi","year":"2018","journal-title":"Int. J. Operat. Res. Inf. Sys."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.cie.2018.02.018","article-title":"A robust and cooperative parallel tabu search algorithm for the maximum vertex weight clique problem","volume":"118","author":"Kiziloz","year":"2018","journal-title":"Comput. Indust. Eng."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/j.cie.2019.04.040","article-title":"An extension of adaptive multi-start tabu search for the maximum quasi-clique problem","volume":"132","author":"Djeddi","year":"2019","journal-title":"Comput. Indust. Eng."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0167-6377(90)90057-C","article-title":"An exact algorithm for the maximum clique problem","volume":"9","author":"Carraghan","year":"1990","journal-title":"Oper. Res. Lett."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/359094.359101","article-title":"New methods to color the vertices of a graph","volume":"22","year":"1979","journal-title":"Commun. ACM"},{"key":"ref_16","unstructured":"(2020, June 17). DIMACS: Clique Benchmark Instances. Available online: http:\/\/iridia.ulb.ac.be\/~fmascia\/maximum_clique\/DIMACS-benchmark."},{"key":"ref_17","unstructured":"Jin, Y., and Hao, J.-K. (2020, June 17). SBTS Software. Available online: http:\/\/www.info.univ-angers.fr\/pub\/hao\/mis.html."},{"key":"ref_18","unstructured":"(2020, June 17). BHOSLIB: Benchmarks with Hidden Optimum Solutions for Graph Problems. Available online: http:\/\/iridia.ulb.ac.be\/~fmascia\/maximum_clique\/BHOSLIB-benchmark."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1007\/s10623-014-9930-z","article-title":"Permutation codes invariant under isometries","volume":"75","author":"Janiszczak","year":"2015","journal-title":"Design. Code. Cryptogr."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/10\/253\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:16:32Z","timestamp":1760177792000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/10\/253"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,4]]},"references-count":19,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2020,10]]}},"alternative-id":["a13100253"],"URL":"https:\/\/doi.org\/10.3390\/a13100253","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,10,4]]}}}