A heuristic based harmony search algorithm for maximum clique problem

Assif Assad () and Kusum Deep ()
Additional contact information
Assif Assad: Indian Institute of Technology Roorkee
Kusum Deep: Indian Institute of Technology Roorkee

OPSEARCH, 2018, vol. 55, issue 2, No 10, 433 pages

Abstract: 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 \times N^3)$$ O ( G × N 3 ) 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.

Keywords: Harmony search; Maximum clique problem; Evolutionary algorithm; Heuristics (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s12597-017-0325-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:opsear:v:55:y:2018:i:2:d:10.1007_s12597-017-0325-6

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/12597

DOI: 10.1007/s12597-017-0325-6

Access Statistics for this article

OPSEARCH is currently edited by Birendra Mandal

More articles in OPSEARCH from Springer, Operational Research Society of India
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().