A DNA algorithm for the graph coloring problem.
A DNA algorithm based on surfaces for the graph coloring problem is presented. First the whole combinatorial color assignments to the vertices of a graph are synthesized and immobilized on a surface; then a vertex is legally colored while those adjacent to it with illegal colors are deleted; and the cycle is repeated until finally the correct color assignments to the graph are reached. Compared with the other DNA algorithms, our algorithm is easy to implement and error-resistant.
Liu
Wenbin
W
Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan City 430074, China. wbliu@mail.hust.edu.an
Zhang
Fengyue
F
Xu
Jin
J
D000465:Algorithms; D003116:Color; D003196:Computer Graphics; D039301:Computers, Molecular