图顶点着色问题的改进粘贴DNA算法  

An Improved DNA Algorithm of Graph Vertex Coloring Problem Based on Sticker Model

作　　者：杨玉星[1] 马季兰[2] 

机构地区：[1]安阳师范学院计算机科学系,河南安阳455000 [2]太原理工大学计算机与软件学院,山西太原030024

出　　处：《太原理工大学学报》2008年第3期285-288,共4页Journal of Taiyuan University of Technology

摘　　要：针对目前存在的解决图顶点着色问题的DNA算法或DNA编码量过大或复杂度太高的问题,为了提高解题效率,将多级分离技术应用到图顶点着色问题的求解中,对解决该问题原有粘贴DNA算法加以改进;改进后的算法减少了操作步骤,达到了预期目的;最后,通过对一个实例的模拟,说明了改进算法的可行性。The existed DNA algorithms of graph vertex-coloring either needed lots of DNA strands or had extortionate complexity. In order to improve the efficiency to solve the problems, the multi-separation techniques were applied to solve the graph vertex-coloring problem, and the former algorithm was improved. The improved algorithm reduced the operating steps. At last, the feasibility of the improved algorithm was proved by a simulation experiment to an instance.

关 键 词：DNA计算 粘贴模型 多级分离 NP-完全问题 图顶点着色 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]