General Information
    • ISSN: 1793-8201 (Print), 2972-4511 (Online)
    • Abbreviated Title: Int. J. Comput. Theory Eng.
    • Frequency: Quarterly
    • DOI: 10.7763/IJCTE
    • Editor-in-Chief: Prof. Mehmet Sahinoglu
    • Associate Editor-in-Chief: Assoc. Prof. Alberto Arteta, Assoc. Prof. Engin Maşazade
    • Managing Editor: Ms. Mia Hu
    • Abstracting/Indexing: Scopus (Since 2022), INSPEC (IET), CNKI,  Google Scholar, EBSCO, etc.
    • Average Days from Submission to Acceptance: 192 days
    • APC: 800 USD
    • E-mail: editor@ijcte.org
    • Journal Metrics:
    • SCImago Journal & Country Rank
Article Metrics in Dimensions

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).

[PDF]

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-2024. International Association of Computer Science and Information Technology. All rights reserved.