Clique Finder: A Self-Adaptive Simulated Annealing Algorithm for the Maximum Clique Problem

Sarab Almuhaideb, Najwa Altwaijry, Shahad AlMansour, Ashwaq AlMklafi, AlBandery Khalid AlMojel, Bushra AlQahtani and Moshail AlHarran
Additional contact information
Sarab Almuhaideb: Department of Computer Science, College of Computer and Information Sciences, King Saud University, Saudi Arabia
Najwa Altwaijry: Department of Computer Science, College of Computer and Information Sciences, King Saud University, Saudi Arabia
Shahad AlMansour: Department of Computer Science, College of Computer and Information Sciences, King Saud University, Saudi Arabia
Ashwaq AlMklafi: Department of Computer Science, College of Computer and Information Sciences, King Saud University, Saudi Arabia
AlBandery Khalid AlMojel: Department of Computer Science, College of Computer and Information Sciences, King Saud University, Saudi Arabia
Bushra AlQahtani: Department of Computer Science, College of Computer and Information Sciences, Saudi Arabia
Moshail AlHarran: Department of Computer Science, College of Computer and Information Sciences, King Saud University, Saudi Arabia

International Journal of Applied Metaheuristic Computing (IJAMC), 2022, vol. 13, issue 2, 1-22

Abstract: The Maximum Clique Problem (MCP) is a classical NP-hard problem that has gained considerable attention due to its numerous real-world applications and theoretical complexity. It is inherently computationally complex, and so exact methods may require prohibitive computing time. Nature-inspired meta-heuristics have proven their utility in solving many NP-hard problems. In this research, we propose a simulated annealing-based algorithm that we call Clique Finder algorithm to solve the MCP. Our algorithm uses a logarithmic cooling schedule and two moves that are selected in an adaptive manner. The objective (error) function is the total number of missing links in the clique, which is to be minimized. The proposed algorithm was evaluated using benchmark graphs from the open-source library DIMACS, and results show that the proposed algorithm had a high success rate.

Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 8/IJAMC.20220401.oa1 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jamc00:v:13:y:2022:i:2:p:1-22

Access Statistics for this article

International Journal of Applied Metaheuristic Computing (IJAMC) is currently edited by Peng-Yeng Yin

More articles in International Journal of Applied Metaheuristic Computing (IJAMC) from IGI Global
Bibliographic data for series maintained by Journal Editor ().