DNA solution of a graph coloring problem.
The graph-theoretic parameter that has probably received the most attention over the years is the chromatic number. As is well-known, the coloring problem is an NP-Complete problem. In this paper, it has been solved by means of molecular biology techniques. The algorithm is highly parallel and has satisfactory fidelity. This work shows further evidence for the ability of DNA computing to solve NP-Complete problems.
Liu
Yachun
Y
Department of Mathematics and Physical Science, Nanhua University Hengyang, Hunan, 421001 P. R. China. liuyachun65@263.net
Xu
Jin
J
Pan
Linqiang
L
Wang
Shiying
S
D001483:Base Sequence; D019295:Computational Biology; D004247:DNA; D008969:Molecular Sequence Data
D004247:DNA