Liu Wenbin, Zhang Fengyue, Xu Jin
Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan City 430074, China.
J Chem Inf Comput Sci. 2002 Sep-Oct;42(5):1176-8. doi: 10.1021/ci025546e.
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.
提出了一种基于表面的用于图着色问题的DNA算法。首先，将图顶点的所有组合颜色分配合成并固定在一个表面上；然后给一个顶点合法着色，同时删除与其相邻的具有非法颜色的顶点；并重复这个循环，直到最终得到图的正确颜色分配。与其他DNA算法相比，我们的算法易于实现且抗错误。
