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

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

Dalila Tayachi (Ecole Supérieure de Commerce de Tunis, Tunis, Tunisia) and Marwa Khemiri (Ecole Supérieure de Commerce de Tunis, Tunis, Tunisia)
DOI: 10.4018/IJORIS.2018100102

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.
Article Preview
Top

Several exact methods, heuristics and metaheuristics have been proposed to solve the maximum clique problem (MCP). For the exact methods, most of them are based on branch and bound framework, for example, an early basic branch and bound algorithm of Carraghan and Pardalos (1990). These methods differ according to their branching strategy or the technique of determination the bounds. Some exact methods are based on solving sub-clique problem such as the method of Ostergard (2002), while others are based on sub-graph coloring like the algorithm of Babel and Tinhofer (1990), Tomita and Kameda (2007). Some are based on Maxsat such as the algorithm of Li and Quan (2010).

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 12: 4 Issues (2021): Forthcoming, Available for Pre-Order
Volume 11: 4 Issues (2020): 3 Released, 1 Forthcoming
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing