| 基于粘贴模型的图顶点着色问题的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 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用》浏览原始摘要信息 |
|
点击此处可从《计算机应用》下载全文 |
|
