Article Preview
Top1. Introduction
Evolutionary Algorithms have been applied to some well-known NP-hard combinatorial problems (Muehlenbein, Gorges-Schleuter & Kraemer,1988) such as the traveling salesman problem (Labadie, Melechovsky & Prins, 2014), the bin packing problem (Blum & Schmid, 2013), the quadratic assignment problem (Maniezzo, Dorigo & Colorni, 1995; Loiolade, Abreu, Boaventura-Netto, Hahn & Querido, 2007) and Knapsack Problem (Chu & Beasley, 1998 ; Gottlieb, 2000). In particular, many evolutionary approaches have been proposed to deal with the graph coloring problem and some other graph coloring parameters (Davis, 1991; Costa, Hertz & Dubuis, 1995; Galinier & Hao, 1999; Ben Mabrouk, Hasni & Mahjoub, 2009; Galinier, Hamiez & Hao, 2013; Chalupa, 2011; Myszkowski, 2008; Consoli, Coller`a & Pavone, 2013). The results obtained by these algorithms are impressive and they constitute a strong indicator that evolutionary algorithms are among the powerful solving tools for hard problems.
In this paper, we are interested in tackling with an evolutionary algorithm a recent graph coloring variant called the strict strong graph coloring (short SSColoring).So, The applicability of evolutionary algorithm in finding good solutions to the presented problem is the main motivation of the present research.
The SSColoring is a new graph coloring problem. It consists in a vertex coloring problem with considering the dominance relation between vertices and color classes. More precisely, the SSColoring consists in coloring the vertices of a given graph with a minimal number of colors called strict strong chromatic number denoted by χss with the constraints that adjacent vertices should receive different colors (i.e. proper coloring) and also each vertex in the graph must dominate at least one non-empty color class (i.e. dominance) (Haddad & Kheddouci, 2009).
The SSColoring problem is defined to embody the use of the dominance property in the strong coloring (short SColoring). The latter is defined by Zverovich (2006). It allows the dominance of the empty color class which hasn’t a sense in practice.
To more explain the assumption, Haddad and Kheddouci (2009) have taken as example the broadcasting application:
In the broadcasting process, one possibility is that every vertex v in the graph forwards the received message to the color class that it dominates. However, as defined by Zverovich (2006), a proper coloring can be seen as a strong coloring where each vertex dominates the empty color class. In this case, if a vertex v dominates an empty color class, then, the messages will never leave the vertex v. unfortunately, the dominance property is useless in this case and the broadcasting of the message fails. For that reason, Haddad and Kheddouci (2009) have proposed the SScoloring which forbids the presence of an empty color class.
The SSColoring concept allows modeling many practical and important applications: