| 图的最小顶点覆盖问题的面上DNA解法 |
| |
| 引用本文： | 王淑栋,许进,董亚非.图的最小顶点覆盖问题的面上DNA解法[J].小型微型计算机系统,2004,25(2):242-244. |
| |
| 作者姓名： | 王淑栋 许进 董亚非 |
| |
| 作者单位： | 1. 华中科技大学,控制科学与工程系,湖北,武汉,430074;山东科技大学,信息科学与工程学院,山东,泰安,271019
2. 华中科技大学,控制科学与工程系,湖北,武汉,430074 |
| |
| 基金项目： | 国家自然科学基金 (60 1740 47，60 2 740 2 6)资助课题 |
| |
| 摘 要： | 1994年，Adleman提出一种解决NP完全问题的新方法-DNA计算．之后又出现了许多关于DNA计算的改进操作并增加了其可靠性，其中面上操作是一种很有效的方法．本文利用DNA计算的固态处理(面上计算)解决了图论中又-NP完全问题一图的最小顶点覆盖问题．构造了含有6个顶点10条边的图的顶点集子集对应的数据池之后，进行了一系列的合成、杂交、清洗、变性等生物操作，得到所有覆盖对应的DNA序列，然后通过编址过程得到所要求的最小覆盖．
|
| 关 键 词： | DNA计算 覆盖 顶点的度 |
| 文章编号： | 1000-1220(2004)02-0242-03 |
A DNA Solution on Surface for Minimal Vertex Covering Problems of Graph |
| |
| WANG Shu-dong ,XU Jin,DONG Ya-fei.A DNA Solution on Surface for Minimal Vertex Covering Problems of Graph[J].Mini-micro Systems,2004,25(2):242-244. |
| |
| Authors: | WANG Shu-dong XU Jin DONG Ya-fei |
| |
| Affiliation: | WANG Shu-dong 1,2,XU Jin1,DONG Ya-fei1 1 |
| |
| Abstract: | In this paper, a model of DNA computing on surface of minimal vertex covering problems of graph is designed a feasible method and operating procedure of biochemical experiment of an example is given. Firstly, we construct a data pool corresponding to the subsets of vertex set of a graph with 6 vertices and 10 edges. Secondly, we proceed a series of biochemical experiments. synthesis, hybridization, cleaning and denaturalization etc. In this way, the DNA sequences corresponding to all the coverings is obtained. Then, we get all the minimal coverings according to the encoding address procedure. |
| |
| Keywords: | DNA computing covering degree of a vertex |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
