An Efficient Evolutionary Algorithm for Strict Strong Graph Coloring Problem

An Efficient Evolutionary Algorithm for Strict Strong Graph Coloring Problem

Meriem Bensouyad (MISC Laboratory, Constantine 2 University, Constantine, Algeria), Nousseiba Guidoum (MISC Laboratory, Constantine 2 University, Constantine, Algeria) and Djamel-Eddine Saïdouni (MISC Laboratory, Constantine 2 University, Constantine, Algeria)
Copyright: © 2014 |Pages: 15
DOI: 10.4018/ijaec.2014040102
OnDemand PDF Download:
List Price: $37.50


A very promising approach for combinatorial optimization is evolutionary algorithms. As an application, this paper deals with the strict strong graph coloring problem defined by Haddad and Kheddouci (2009) where the authors have proposed an exact polynomial time algorithm for trees. The aim of this paper is to introduce a new evolutionary algorithm for solving this problem for general graphs. It combines an original crossover and a powerful correction operator. Experiments of this new approach are carried out on large Dimacs Challenge benchmark graphs. Results show very competitive with and even better than those of state of the art algorithms. To the best of the author's knowledge, it is the first time that an evolutionary algorithm is proposed to solve the strict strong graph coloring problem.
Article Preview

1. 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:

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2017): 3 Released, 1 Forthcoming
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing