图的最小顶点覆盖问题的面上DNA解法

摘要：

1994年,Adleman 提出一种解决NP完全问题的新方法-DNA计算.之后又出现了许多关于DNA计算的改进操作并增加了其可靠性,其中面上操作是一种很有效的方法.本文利用DNA计算的固态处理(面上计算)解决了图论中又一NP完全问题-图的最小顶点覆盖问题.构造了含有6个顶点10条边的图的顶点集子集对应的数据池之后,进行了一系列的合成、杂交、清洗、变性等生物操作,得到所有覆盖对应的DNA序列,然后通过编址过程得到所要求的最小覆盖.

关键词：DNA计算、覆盖、顶点的度

所属期刊栏目：25

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

资助基金：国家自然科学基金60174047,60274026

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

页数：共3页

页码：242-244