Skip navigation
Please use this identifier to cite or link to this item:
Title: A heuristic based harmony search algorithm for maximum clique problem
Authors: Assad A.
Deep, K.
Published in: OPSEARCH
Abstract: The maximum clique problem (MCP) is to determine a complete subgraph (clique) of maximum cardinality in a given graph. MCP is conspicuous for having real world applications and for its potentiality of modeling other combinatorial problems and is one of the most studied NP-hard problems. This paper investigates the capabilities of Harmony Search (HS) algorithm, a music inspired meta heuristic for solving maximum clique problem. We propose and compare two different instantiations of a generic HS algorithm namely Harmony Search for MCP (HS_MCP) and Harmony Search with idiosyncratic harmonies for MCP (HSI_MCP) for this problem. HS_MCP has better exploitation and inferior exploration capabilities than HSI_MCP whereas HSI_MCP has better exploration and inferior exploitation capabilities than HSI_MCP, it has been concluded that former performs better than latter by testing them on all the instances of DIMACS benchmark graphs. HS_MCP has been compared with a recently proposed Harmony search based algorithm for MCP called Binary Harmony search (BHS) and the simulation results show that HS_MCP significantly outperforms BHS in terms of solution quality. The asymptotic time complexity of HS_MCP is O(G× N3) where G is the number of generations and N is the number of nodes in the graph. A glimpse of effectiveness of some state-of-the-art exact algorithms on MCP has also been provided. © 2017, Operational Research Society of India.
Citation: OPSEARCH (2018), 55(2): 411-433
Issue Date: 2018
Publisher: Springer India
Keywords: Evolutionary algorithm
Harmony search
Maximum clique problem
ISSN: 303887
Author Scopus IDs: 57189041771
Author Affiliations: Assad, A., Department of Mathematics, Indian Institute of Technology Roorkee, Roorkee, 247667, India
Deep, K., Department of Mathematics, Indian Institute of Technology Roorkee, Roorkee, 247667, India
Funding Details: Acknowledgements The first author would like to acknowledge QIP Centre Indian Institute of Technology Roorkee, India and All India Council for Technical Education (AICTE) for sponsoring his research.
Corresponding Author: Assad, A.; Department of Mathematics, Indian Institute of Technology RoorkeeIndia; email:
Appears in Collections:Journal Publications [MA]

Files in This Item:
There are no files associated with this item.
Show full item record

Items in Repository are protected by copyright, with all rights reserved, unless otherwise indicated.