The IRMA Community
Newsletters
Research IRM
Click a keyword to search titles using our InfoSci-OnDemand powered search:
|
An Efficient Evolutionary Algorithm for Strict Strong Graph Coloring Problem
|
|
Author(s): 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
Source title:
Research Methods: Concepts, Methodologies, Tools, and Applications
Source Author(s)/Editor(s): Information Resources Management Association (USA)
DOI: 10.4018/978-1-4666-7456-1.ch086
Purchase
|
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.
Related Content
|
Tutita M. Casa, Fabiana Cardetti, Madelyn W. Colonnese.
© 2024.
14 pages.
|
|
R. Alex Smith, Madeline Day Price, Tessa L. Arsenault, Sarah R. Powell, Erin Smith, Michael Hebert.
© 2024.
19 pages.
|
|
Marta T. Magiera, Mohammad Al-younes.
© 2024.
27 pages.
|
|
Christopher Dennis Nazelli, S. Asli Özgün-Koca, Deborah Zopf.
© 2024.
31 pages.
|
|
Ethan P. Smith.
© 2024.
22 pages.
|
|
James P. Bywater, Sarah Lilly, Jennifer L. Chiu.
© 2024.
20 pages.
|
|
Ian Jones, Jodie Hunter.
© 2024.
20 pages.
|
|
|