Complexity Analysis and Stochastic Convergence of Some Well-known Evolutionary Operators for Solving Graph Coloring Problem

Raja Marappan and Gopalakrishnan Sethumadhavan
Additional contact information
Raja Marappan: Department of Computer Applications, School of Computing, SASTRA Deemed University, Tirumalaisamudram 613401, India
Gopalakrishnan Sethumadhavan: Department of Computer Applications, School of Computing, SASTRA Deemed University, Tirumalaisamudram 613401, India

Mathematics, 2020, vol. 8, issue 3, 1-20

Abstract: The graph coloring problem is an NP -hard combinatorial optimization problem and can be applied to various engineering applications. The chromatic number of a graph G is defined as the minimum number of colors required to color the vertex set V ( G ) so that no two adjacent vertices are of the same color, and different approximations and evolutionary methods can find it. The present paper focused on the asymptotic analysis of some well-known and recent evolutionary operators for finding the chromatic number. The asymptotic analysis of different crossover and mutation operators helps in choosing the better evolutionary operator to minimize the problem search space and computational complexity. The choice of the right genetic operators facilitates an evolutionary algorithm to achieve faster convergence with lesser population size N through an adequate distribution of promising genes. The selection of an evolutionary operator plays an essential role in reducing the bounds for minimum color obtained so far for some of the benchmark graphs. This research also focuses on the necessary and sufficient conditions for the global convergence of evolutionary algorithms. The stochastic convergence of recent evolutionary operators for solving graph coloring is newly analyzed.

Keywords: approximation methods; chromatic number; combinatorial optimization; complexity analysis; evolutionary approach; genetic algorithm; graph coloring; NP -hard; stochastic convergence (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/3/303/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/3/303/ (text/html)

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:gam:jmathe:v:8:y:2020:i:3:p:303-:d:324756

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().