首页 | 本学科首页   官方微博 | 高级检索  
     

基于粘贴模型的图顶点着色问题的DNA算法
引用本文:马季兰,杨玉星. 基于粘贴模型的图顶点着色问题的DNA算法[J]. 计算机应用, 2006, 26(12): 2998-3000
作者姓名:马季兰  杨玉星
作者单位:太原理工大学,计算机与软件学院,山西,太原,030024;太原理工大学,计算机与软件学院,山西,太原,030024
摘    要:为了用生化实验的方法解决图的顶点着色问题,基于粘贴模型的巨大并行性,将着色问题转化为可满足性问题,提出一个基于粘贴模型的DNA算法。通过一个实例给出了操作步骤,并对生化反应过程进行了模拟,得出具体的着色方案,证明了该算法的可行性。

关 键 词:DNA计算  粘贴模型  NP-完全问题  图顶点着色
文章编号:1001-9081(2006)12-2998-03
收稿时间:2006-06-26
修稿时间:2006-06-262006-08-21

DNA algorithm of graph vertex coloring problem based on sticker model
Ma Ji-lan,Yang Yu-xing. DNA algorithm of graph vertex coloring problem based on sticker model[J]. Journal of Computer Applications, 2006, 26(12): 2998-3000
Authors:Ma Ji-lan  Yang Yu-xing
Affiliation:College of Computer and Software, Taiyuan University of Technology, Taiyuan Shanxi 030024, China
Abstract: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.
Keywords:DNA computing   sticker model   NP-eomplete problem   vertex-coloring of graph
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《计算机应用》浏览原始摘要信息
点击此处可从《计算机应用》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号