图的最小顶点覆盖问题的DNA表面计算模型

摘要：

基于生化反应原理的DNA计算具有强大的并行运算能力,DNA计算机在求解NP问题上存在着硅计算机无法比拟的先天的优越性.采用荧光标记的策略,给出了一种新的图的最小顶点覆盖问题的DNA表面计算模型.该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得图的最小顶点覆盖问题的所有解.新算法利用荧光猝灭技术,通过观察荧光来排除非解,具有编码、解读简单和错误率低的特点.

关键词：DNA计算、表面方式、解空间、顶点覆盖

所属期刊栏目：45

分类号：TP301(计算技术、计算机技术)

资助基金：湖南省教育厅科研项目the Scientific Research Fundation of Hunan Province Education Department under Grant 06C439;湖南省"十一五"计算机应用技术重点建设学科支持

在线出版日期：2009-04-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：69-72