• Mar 05, 2019 News!Vol.11, No.1 has been published with online version.   [Click]
  • Aug 06, 2018 News!Vol.9, No.1-Vol.9, No.4 have been indexed by EI (Inspec).   [Click]
  • Dec 29, 2018 News!Vol.10, No.6 has been published with online version.   [Click]
General Information
Prof. Wael Badawy
Department of Computing and Information Systems Umm Al Qura University, Canada
I'm happy to take on the position of editor in chief of IJCTE. We encourage authors to submit papers concerning any branch of computer theory and engineering.
IJCTE 2013 Vol.5(6): 890-894 ISSN: 1793-8201
DOI: 10.7763/IJCTE.2013.V5.817

Memetic Algorithm to Solve Graph Coloring Problem

Hasin Al Rabat Chowdhury, Tasneem Farhat, and Mozammel H. A. Khan
Abstract—Graph coloring problem (GCP) is of great interest to the researchers in the area of soft computing. To solve GCP, we present a memetic algorithm (MA) that uses classical crossover operation as the main variation operator and a deterministic local improvement technique. For the first time in the literature, we use binary encoded chromosomes for GCP, which makes both the crossover and the local improvement easier. In the traditional evolutionary algorithm (EA) for GCP, k-coloring is used and the EA is run repeatedly until the lowest possible k is reached. In our MA, we start with the theoretical upper bound of chromatic number (maximum out-degree + 1) and in the process of evolution some of the colors are made unused to dynamically reduce the number of color. Thus, the solution is found in a single run of the MA reducing the total execution time in comparison to running k-coloring for several times. We experiment with 23 datasets taken from standard DIMACS benchmark and compare the result with several recent works. For all but one dataset, we obtain the minimum chromatic number stated in the DIMACS benchmark. For the remaining one dataset (queen10_10.col), we obtain better solution than others.

Index Terms—Binary encoding, dynamicity, graph coloring, local improvement, memetic algorithm, metaheuristics.

H. A. R. Chowdhury, T. Farhat, and M. H. A. Khan are with Department of Computer Science and Engineering, East West University, Aftabnagar, Dhaka 1212, Bangladesh (e-mail: hrcrabat@gmail.com, lvuplf@gmail.com, mhakhan@ewubd.edu).


Cite:Hasin Al Rabat Chowdhury, Tasneem Farhat, and Mozammel H. A. Khan, "Memetic Algorithm to Solve Graph Coloring Problem," International Journal of Computer Theory and Engineering vol. 5, no. 6, pp. 890-894, 2013.

Copyright © 2008-2019. International Journal of Computer Theory and Engineering. All rights reserved.
E-mail: ijcte@iacsitp.com