| 基于剪接系统的有向哈密顿路问题分析 |
| |
| 引用本文： | 王淑栋,许进,刘文斌.基于剪接系统的有向哈密顿路问题分析[J].电子学报,2005,33(5):774-777. |
| |
| 作者姓名： | 王淑栋 许进 刘文斌 |
| |
| 作者单位： | 山东科技大学信息科学与工程学院,山东泰安,271019;华中科技大学控制科学与工程系,湖北武汉,430074;华中科技大学控制科学与工程系,湖北武汉,430074 |
| |
| 摘 要： | 首先给出了剪接系统模拟有向哈密顿路问题的思想;然后通过此剪接系统所产生语言的性质对有向哈密顿路问题进行分析,给出了有向图存在哈密顿路的充要条件.在我们的构造中,模拟问题的剪接系统至多运行n-2步,其中n是模拟问题的规模.
|
| 关 键 词： | DNA计算 剪接系统 有向哈密顿路问题 |
| 文章编号： | 0372-2112(2005)05-0774-04 |
| 收稿时间： | 2004-05-14 |
Analysis for Directed Hamilton Path Problems Based on Splicing Systems |
| |
| WANG Shu-dong,XU Jin,LIU Wen-bin.Analysis for Directed Hamilton Path Problems Based on Splicing Systems[J].Acta Electronica Sinica,2005,33(5):774-777. |
| |
| Authors: | WANG Shu-dong XU Jin LIU Wen-bin |
| |
| Affiliation: | 1. College of Information Science & Engineering,Shandong University of Science and Technology,Taian,Shandong 271019,China;2. Dept of Control Science & Engineering,Huazhong University of Science and Technology,Wuhan,Hubei 430074,China |
| |
| Abstract: | The ideas of simulating directed Hamilton path problems by splicing systems are showed;then some properties of directed graphs are presented based on the analysis of directed Hamilton path problems according to the properties of languages generated by the splicing systems.In our construction,the splicing systems simulating problems run at most n-2 steps,where n is the size of problems. |
| |
| Keywords: | DNA computing splicing system directed Hamilton path problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《电子学报》浏览原始摘要信息 |
|
点击此处可从《电子学报》下载全文 |
|
