Article Preview
Top1. Introduction
The Graph Coloring Problem (GCP) is a very well-known NP-Hard combinatorial optimization problem in computer science, mathematics, and operations research. It deals with assigning a color to each node of a given graph with the restriction that no two adjacent nodes are colored with the same color and that the number of different colors used is minimized. The minimum number of colors by which a graph can be colored is called its chromatic number and it is denoted by χ(G). A graph G is K-colorable if it can be legally colored with at most K colors. The graph coloring problem has recently drawn an increasing attention from researchers and has been widely used to model and solve many significant real-world problems, such as time tabling (de Werra, 1985), scheduling (Lotfi & Sarin, 1986; Dowsland & Thompson, 2005), computer register allocation (Chaitin, Cocke, Hopkins, & Markstein, 1981), (de Werra, Eisenbeis, Lelait, & Marmol, 1999), radio frequency assignment (Gamst, 1986), (Smith, Hurley, & Thiel, 1998), printed circuit board-testing (Garey, Johnson, & So, 1976), noise reduction in VLSI circuits (Maitra, Pal, Bhattacharyya, & Kim, 2010), channel routing (Sen Sarma, Mandal, & Seth, 1994), and communication networks (Woo, Su, & Newman-Wolfe, 1991).
Several approaches have been adopted in solving this problem including greedy constructive approaches, local search heuristics, meta-heuristics and hybrid approaches.
The two most constructive algorithms employed to solve the GCP are the recursive largest first algorithm (RLF) proposed by Leighton (Leighton, 1979) and the largest saturation degree algorithm (DSATUR) developed by Brélaz (Brélaz, 1979). These methods are based on greedy approach which colors the nodes of the graph one at time using a predefined greedy function. Recently, these approaches have been used to generate initial solutions for advanced evolutionary algorithms.
Local search heuristics have been widely proposed to solve the GCP. Tabu Search Algorithm proposed by Hertz and de Werra (Hertz & de Werra, 1987) was the first local search algorithm applied to solve the graph coloring problem. It is called TABUCOL and has been improved by several researchers and used as a subcomponent of more graph coloring algorithms.
Moreover, many efficient meta-heuristics such as Genetic Algorithm (GA) (Abbasian & Mouhoub, 2013), Cuckoo Search algorithm (CS) (Mahmoudi & Lotfi, 2015), Artificial Bee Colony (ABC) (Faraji & Javadi, 2011), Ant Based Algorithm(ABA) (Bui, Nguyen, Patel, & Phan, 2008), Particle Swarm Optimization (PSO) (Agrawal & Agrawal, 2015), Bat Algorithm (BA) (Djelloul, Sabba, & Chikhi, 2014), Memetic Algorithm (MA) (Lü & Hao, 2010), Firefly Algorithm (FA) (Chen & Kanoh, 2017), and combining algorithms (Douiri & Elbernoussi, 2015; Marappan & Sethumadhavan, 2018) have been employed in solving the Graph coloring problem.
Abbasian and Mouhoub (Abbasian & Mouhoub, 2013) proposed a Hierarchical approach based on Parallel Genetic Algorithms (HPGAs) for solving the GCP. In this approach, a novel estimator is implemented to predict an upper-bound for the graph’s chromatic number. Furthermore, an extension of the genetic algorithm, namely the Genetic Modification (GM) and the parental success crossover operator have been proposed. Experimental results showed that the proposed approach was very accurate and faster in solving this problem.