The chromatic number of a graph G is the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color. Calculating the chromatic number of a graph is an NP-complete problem and no convenient method is known for determining the chromatic number of an arbitrary graph.
Published in Chapter:
Hybrid Genetic Approach for Solving Fuzzy Graph Coloring Problem
Mohamed Amine Basmassi (ISO Laboratory, Faculty of Sciences, Ibn Tofail University, Morocco), Sidina Boudaakat (SSDIA Laboratory, ENSET Mohammedia, Hassan II University of Casablanca, Morocco), Lamia Benameur (LIROSA Laboratory, Faculty of Sciences, Abdelmalik Essaadi University, Morocco), Omar Bouattane (SSDIA Laboratory, ENSET Mohammedia, Hassan II University of Casablanca, Morocco), Ahmed Rebbani (SSDIA Laboratory, ENSET Mohammedia, Hassan II University of Casablanca, Morocco), and Jihane Alami Chentoufi (ISO Laboratory, Faculty of Sciences, Ibn Tofail University, Morocco)
Copyright: © 2020
|Pages: 11
DOI: 10.4018/978-1-7998-4381-8.ch003
Abstract
A hybrid genetic approach (HGA) is proposed to solve the fuzzy graph coloring problem. The proposed approach integrates a number of new features, such as an adapted greedy sequential algorithm, which is integrated in genetic algorithm to increase the quality of chromosomes and improve the rate of convergence toward the chromatic number. Moreover, an upper bound is used to generate the initial population in order to reduce the search space. Experiments on a set of five well-known DIMACS benchmark instances show that the proposed approach achieves competitive results and succeeds in finding the global optimal solution rapidly for complex fuzzy graph.