A Novel Presentation of Graph Coloring Problems Based on Parallel Genetic Algorithm
Saideh Naderi1, Masoud Jabbarian2, Vahid Sattari Naeini3
1Saideh naderi, Department of Computer Engineering, Kerman Branch, Islamic Azad University, Kerman, Iran.
2Masoud jabbarian, Department of Computer Engineering, Kerman Branch, Islamic Azad University, Kerman, Iran.
3Vahid Sattari Naeini, Department of Computer Engineering, University of Kerman, Kerman, Iran.
Manuscript received on June 05, 2013. | Revised Manuscript received on June 29, 2013. | Manuscript published on July 05, 2013. | PP: 65-70 | Volume-3 Issue-3, July 2013. | Retrieval Number: C1604073313/2013©BEIESP
Open Access | Ethics and Policies | Cite
© The Authors. Published By: Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: In coloring graph idealization the minimum number of required colors for graphic coloring is determined in a way that no contiguous summit have the same color this number is called chromatic graph number. We should decide if then, a color for a given integral number M , so we use that number with no contiguous summits of the same color there have been presented several algorithms for decision and idealization manners so for such as: reverse counting method ,space mood counting method and etc…that don’t follow multi statement time. Here by in this paper we present suitable solutions for this problem by genetic algorithm. In order to evaluate the performance of our new approach, we have conducted several experiments on GCP instances taken from the well known DIMACS Website. The results show that the proposed approach has a high performance in time and quality of the solution returned in solving graph coloring instances taken from DIMACS website. The quality of the solution is measured here by comparing the returned solution with the optimal one.
Keywords: Graph Coloring Problems (GCPs), Parallel Genetic Algorithms (PGAS), NP-hard, chromosome.