|
|||||
|
|
| 图的最小顶点覆盖问题的DNA表面计算模型 | |
| 引用本文： | 羊四清,李小龙,袁辉勇.图的最小顶点覆盖问题的DNA表面计算模型[J].计算机工程与应用,2009,45(6):69-72. |
| 作者姓名： | 羊四清 李小龙 袁辉勇 |
| 作者单位： | 1. 湖南人文科技学院,湖南,娄底,417000;湖南大学,计算机与通信学院,长沙,410082 2. 湖南大学,计算机与通信学院,长沙,410082 3. 湖南人文科技学院,湖南,娄底,417000 |
| 基金项目： | 湖南省教育厅科研项目，湖南省计算机应用技术重点建设学科支持项目 |
| 摘 要： | 基于生化反应原理的DNA计算具有强大的并行运算能力,DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性。采用荧光标记的策略,给出了一种新的图的最小顶点覆盖问题的DNA表面计算模型。该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得图的最小顶点覆盖问题的所有解。新算法利用荧光猝灭技术,通过观察荧光来排除非解,具有编码、解读简单和错误率低的特点。 |
| 关 键 词： | DNA计算 表面方式 解空间 顶点覆盖 |
| 收稿时间： | 2008-1-14 |
| 修稿时间： | 2008-4-10 |
Surface-based DNA algorithm for minimal vertex covering problem |
|
| YANG Si-qing,LI Xiao-long,YUAN Hui-yong.Surface-based DNA algorithm for minimal vertex covering problem[J].Computer Engineering and Applications,2009,45(6):69-72. | |
| Authors: | YANG Si-qing LI Xiao-long YUAN Hui-yong |
| Affiliation: | YANG Si-qing1,2,LI Xiao-long2,YUAN Hui-yong11.Hunan Institute of Humanities,Science , Technology,Loudi,Hunan 417000,China 2.College of Computer , Communication,Hunan University,Changsha 410082,China |
| Abstract: | Biochemical reaction theory based DNA computation is of the massive inherent parallelism,so compared to silicon computer,DNA computer has most superiority out and away on NP problems.This paper proposes a new DNA algorithm of minimal vertex covering problem based surface by using the method of fluorescence labeling.The DNA molecules of the solution space are fixed on the solid carrier,and then get the all solutions of minimal vertex covering problem by the biochemical actions.The new algorithm utilizes the ... |
| Keywords: | DNA computing surface-based fashion solution space vertex covering |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 | |
| 点击此处可从《计算机工程与应用》下载全文 | |
