A Parallel Hybrid Genetic Algorithm for Solving the Maximum Clique Problem

Mohammad Kazem Fallah, Vahid Salehi Keshvari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

Finding maximum complete subgraph (maximum clique) from the input graph is an NP-Complete problem. When the graph size grows, the genetic algorithm is an appropriate candidate for solving this problem. However, due to the reduced computational complexity, the genetic algorithm can solve the problem, but it can still be time consuming to solve big problems. To tackle this weakness, we parallelize our hybrid genetic algorithm for solving the maximum clique problem. In this direction, we have parallelized producing, repairing and evaluation of chromosomes. Experimental results by using a set of benchmark instances from the DIMACS graphs indicate that the proposed meta heuristic algorithm in almost all cases, it finds optimal or near optimal answer. Also, the efficiency of the proposed parallelization is more than 3.44 times faster on an 8-core processor in comparison to the sequential implementation.

Original languageEnglish
Title of host publicationHigh-Performance Computing and Big Data Analysis- 2nd International Congress, TopHPC 2019, Revised Selected Papers
EditorsLucio Grandinetti, Reza Shahbazian, Seyedeh Leili Mirtaheri
PublisherSpringer Nature Link
Pages378-393
Number of pages16
ISBN (Print)9783030334949
DOIs
Publication statusPublished - 2019
Externally publishedYes
Event2nd International Congress on High-Performance Computing and Big Data Analysis, TopHPC 2019 - Tehran, Iran, Islamic Republic of
Duration: 23 Apr 201925 Apr 2019

Publication series

NameCommunications in Computer and Information Science
Volume891
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937

Conference

Conference2nd International Congress on High-Performance Computing and Big Data Analysis, TopHPC 2019
Country/TerritoryIran, Islamic Republic of
CityTehran
Period23/04/1925/04/19

Keywords

  • Genetic algorithm
  • Maximum clique problem
  • Parallel algorithm

Fingerprint

Dive into the research topics of 'A Parallel Hybrid Genetic Algorithm for Solving the Maximum Clique Problem'. Together they form a unique fingerprint.

Cite this