A novel discrete particle swarm optimization algorithm for solving graph coloring problem

作者：Zhang Kai; Zhu Wanying; Liu Jun; He Juanjuan^*

来源：Journal of Computational and Theoretical Nanoscience, 2016, 13(6): 3588-3594.

DOI：10.1166/jctn.2016.5187

• Computational time
• Discrete particle swarm optimization algorithm
• Discrete problems
• Discrete state space
• Engineering fields
• Feasible solution
• Graph coloring problem
• Particle swarm optimization algorithm

Graph coloring problem is a well-known NP-complete problem in graph theory. Because GCP often finds its applications to various engineering fields, it is very important to find a feasible solution quickly. In this paper, we present a novel discrete particle swarm optimization algorithm to solve the GCP. In order to apply originally particle swarm optimization algorithm to discrete problem, we design and redefine the crucial position and velocity operators on discrete state space. Moreover, the performance of our algorithm is compared with other published method using 30 DIMACS benchmark graphs. The comparison result shows that our algorithm is more competitive with less chromatic numbers and less computational time.

• 出版日期2016
• 单位武汉科技大学