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, Marwa Khemiri
Copyright: © 2018 |Pages: 15
DOI: 10.4018/IJORIS.2018100102
OnDemand:
(Individual Articles)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

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
Volume 15: 1 Issue (2024)
Volume 14: 1 Issue (2023)
Volume 13: 2 Issues (2022)
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
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