TY - GEN
T1 - A Parallel Hybrid Genetic Algorithm for Solving the Maximum Clique Problem
AU - Fallah, Mohammad Kazem
AU - Keshvari, Vahid Salehi
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
KW - Genetic algorithm
KW - Maximum clique problem
KW - Parallel algorithm
UR - http://www.scopus.com/inward/record.url?scp=85075815835&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-33495-6_29
DO - 10.1007/978-3-030-33495-6_29
M3 - Conference contribution
AN - SCOPUS:85075815835
SN - 9783030334949
T3 - Communications in Computer and Information Science
SP - 378
EP - 393
BT - High-Performance Computing and Big Data Analysis- 2nd International Congress, TopHPC 2019, Revised Selected Papers
A2 - Grandinetti, Lucio
A2 - Shahbazian, Reza
A2 - Mirtaheri, Seyedeh Leili
PB - Springer Nature Link
T2 - 2nd International Congress on High-Performance Computing and Big Data Analysis, TopHPC 2019
Y2 - 23 April 2019 through 25 April 2019
ER -