An Efficient Evolutionary Algorithm for Strict Strong Graph Coloring Problem

Meriem Bensouyad, Nousseiba Guidoum and Djamel-Eddine Saïdouni
Additional contact information
Meriem Bensouyad: MISC Laboratory, Constantine 2 University, Constantine, Algeria
Nousseiba Guidoum: MISC Laboratory, Constantine 2 University, Constantine, Algeria
Djamel-Eddine Saïdouni: MISC Laboratory, Constantine 2 University, Constantine, Algeria

International Journal of Applied Evolutionary Computation (IJAEC), 2014, vol. 5, issue 2, 22-36

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

Date: 2014
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/ijaec.2014040102 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jaec00:v:5:y:2014:i:2:p:22-36

Access Statistics for this article

International Journal of Applied Evolutionary Computation (IJAEC) is currently edited by Sukhpal Singh Gill

More articles in International Journal of Applied Evolutionary Computation (IJAEC) from IGI Global
Bibliographic data for series maintained by Journal Editor ().