Affiliations: [a] State Key Laboratory of Simulation and Regulation of River Basin Water Cycle, China Institute of Water Resources and Hydropower Research, Beijing, P. R. China | [b] College of Information, Shanghai Ocean University, Shanghai, P. R. China | [c] School of Information Engineering, Wenzhou Business College, Wenzhou, P. R. China
Correspondence:
[*]
Corresponding author. Tunhua Wu, School of Information Engineering, Wenzhou Business College, Wenzhou 325035, P. R. China. E-mail: appll188@163.com.
Abstract: The vertex coloring problem is a well-known combinatorial problem that requires each vertex to be assigned a corresponding color so that the colors on adjacent vertices are different, and the total number of colors used is minimized. It is a famous NP-hard problem in graph theory. As of now, there is no effective algorithm to solve it. As a kind of intelligent computing algorithm, DNA computing has the advantages of high parallelism and high storage density, so it is widely used in solving classical combinatorial optimization problems. In this paper, we propose a new DNA algorithm that uses DNA molecular operations to solve the vertex coloring problem. For a simple n-vertex graph and k different kinds of color, we appropriately use DNA strands to indicate edges and vertices. Through basic biochemical reaction operations, the solution to the problem is obtained in the O (kn2) time complexity. Our proposed DNA algorithm is a new attempt and application for solving Nondeterministic Polynomial (NP) problem, and it provides clear evidence for the ability of DNA calculations to perform such difficult computational problems in the future.
Keywords: NP-hard problem, the vertex coloring problem, Adleman-Lipton model, DNA computating
