Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Meriem Bensouyad (MISC Laboratory, Constantine 2 University, Algeria), Nousseiba Guidoum (MISC Laboratory, Constantine 2 University, Algeria) and Djamel-Eddine Saïdouni (MISC Laboratory, Constantine 2 University, Algeria)

Copyright: © 2015
|Pages: 14

DOI: 10.4018/978-1-4666-7456-1.ch086

Chapter Preview

TopEvolutionary 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:

Haddad, Dekar, and Kheddouci (2008) have proposed an efficient distributed algorithm based on the SSColoring parameter for the broadcast applications in ad hoc networks. Also, Guidoum, Bensouyad, and Saidouni (2013) proved the usefulness of SSColoring concept to deal with the graph distribution problem. The latter represents one of the most studied problems in the literature.

In addition, such coloring parameter ought to be useful to many other applications like gossiping, data dissemination and scheduling.

The rest of the paper is organized as follows: First, the related works are reviewed in Section 2. Then, Section 3 gives necessary notations and definitions. Section 4 describes the proposed algorithm and details its different components. Section 5 illustrates computational results of the algorithm and gives some discussions. To close, conclusion and perspectives are given in the last section.

Search this Book:

Reset

Copyright © 1988-2018, IGI Global - All Rights Reserved