Open AccessClique Finder
Publication year - 2022
Publication title -
international journal of applied metaheuristic computing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.158
H-Index - 4
eISSN - 1947-8291
pISSN - 1947-8283
DOI - 10.4018/ijamc.20220401oa01
Subject(s) - clique problem , heuristics , clique , computer science , simulated annealing , benchmark (surveying) , mathematical optimization , algorithm , theoretical computer science , mathematics , graph , combinatorics , pathwidth , geodesy , line graph , geography , operating system
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.