Related Experiment Videos
A DNA algorithm for the graph coloring problem
Wenbin Liu1, Fengyue Zhang, Jin Xu
1Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan City 430074, China. wbliu@mail.hust.edu.an
Journal of Chemical Information and Computer Sciences
|October 16, 2002
Abstract:
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.