基于粘贴模型的图顶点着色问题的DNA算法  

DNA algorithm of graph vertex coloring problem based on sticker model

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

机构地区：[1]太原理工大学计算机与软件学院,山西太原030024

出　　处：《计算机应用》2006年第12期2998-3000,共3页journal of Computer Applications

摘　　要：为了用生化实验的方法解决图的顶点着色问题,基于粘贴模型的巨大并行性,将着色问题转化为可满足性问题,提出一个基于粘贴模型的DNA算法。通过一个实例给出了操作步骤,并对生化反应过程进行了模拟,得出具体的着色方案,证明了该算法的可行性。In order to solve the graph vertex-coloring problem, a DNA algorithm based on sticker model was proposed, which converted the coloring problem to satisfiability problem on the basis of the vast parallelism. The operation steps were given through an instance. And a simulation experiment was carried out to illustrate the biochemical procedures. The final coloring schemes were got. Consequently, the feasibility of the algorithm is proved.

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

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