Solving the Maximum Clique Problem using a Hybrid Particle Swarm Optimization Algorithm

Dalila Tayachi and Marwa Khemiri
Additional contact information
Dalila Tayachi: Ecole Supérieure de Commerce de Tunis, Tunis, Tunisia
Marwa Khemiri: Ecole Supérieure de Commerce de Tunis, Tunis, Tunisia

International Journal of Operations Research and Information Systems (IJORIS), 2018, vol. 9, issue 4, 21-35

Abstract: This article tackles the maximum clique problem MCP known as an NP-hard graph problem. The maximum clique problem consists in finding in an undirected graph a complete sub-graph (clique) of maximum cardinality. As the MCP is a classical graph problem extensively studied, the main contribution of this paper is to use for the first time particle swarm to solve it. A hybrid particle swarm optimization algorithm HPSOD is proposed. First a PSO algorithm is designed, based on a sub-graph extraction approach named circular-arc graph CAG, then a local search heuristic is integrated to enhance its performance. Experimental tests carried out on DIMACS benchmarks show a globally good performance of the proposed algorithm and that it outperforms many existent approaches.

Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 18/IJORIS.2018100102 (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:joris0:v:9:y:2018:i:4:p:21-35

Access Statistics for this article

International Journal of Operations Research and Information Systems (IJORIS) is currently edited by John Wang

More articles in International Journal of Operations Research and Information Systems (IJORIS) from IGI Global
Bibliographic data for series maintained by Journal Editor ().