| 基于Tile自组装模型的最大匹配问题算法研究 |
| |
| 引用本文： | 周旭,周炎涛,李肯立,欧阳艾嘉,潘果.基于Tile自组装模型的最大匹配问题算法研究[J].电子学报,2015,43(2):262-268. |
| |
| 作者姓名： | 周旭 周炎涛 李肯立 欧阳艾嘉 潘果 |
| |
| 作者单位： | 1. 嘉兴学院数理与信息工程学院, 浙江嘉兴 314001;
2. 湖南大学信息科学与工程学院, 湖南长沙 410082;
3. 湖南大学电气与信息工程学院, 湖南长沙 410082 |
| |
| 基金项目： | 国家自然科学基金重点项目(No ．61133005)；国家自然科学基金(No ．61173013，No ．61202109)；湖南省杰出青年基金(No ．12JJ1011)；浙江省教育厅科研计划项目(No ．Y201226110)；湖南省科技厅科技计划项目(No ．2013GK3082，No ．2014GK3043)；湖南省教育厅项目 |
| |
| 摘 要： | Tile自组装模型作为一种重要的DNA计算模型,在解决NP问题时展现出了巨大优势.文中针对现有最大匹配问题DNA计算算法实验操作复杂,错误率高的缺点,提出了一种基于Tile自组装模型的最大匹配问题新算法.算法所需的Tile分子种类为O(mn),所需生物操作数为O(1),计算时间为O(m),计算空间复杂度为O(mn)(其中m为边数,n为顶点数,且O(m)=O(n2)).与现有的最大匹配问题DNA计算算法相比,本算法不仅可靠性更好,而且更具可操作性.
|
| 关 键 词： | DNA计算 Tile自组装模型 最大匹配问题 NP完全问题 并行计算 |
| 收稿时间： | 2013-09-18 |
Efficient Maximum Matching Problem Algorithms in the Tile Assembly Model |
| |
| ZHOU Xu,ZHOU Yan-tao,LI Ken-li,OUYANG Ai-jia,PAN Guo.Efficient Maximum Matching Problem Algorithms in the Tile Assembly Model[J].Acta Electronica Sinica,2015,43(2):262-268. |
| |
| Authors: | ZHOU Xu ZHOU Yan-tao LI Ken-li OUYANG Ai-jia PAN Guo |
| |
| Institution: | 1. College of Mathematics and Information Engineering, Jiaxing University, Jiaxing, Zhejiang 314001, China;
2. College of Information Science and Engineering, Hunan University, Changsha, Hunan 410082, China;
3. College of Electrical and Information Engineering, Hunan University, Changsha, Hunan 410082, China |
| |
| Abstract: | The tile self-assembly model is an important DNA computing model.It's useful for handling the NP problem.Currently,when using the DNA computing to solve the maximum matching problem,it will be hard to experiment and easy to make mistakes.Therefore,based on the tile self-assembly model,a new algorithm for the maximum matching problem is designed.The present algorithm needs O(mn) types of tile molecular,its bio-operation is O(1),the computing time is O(m) and space complexity is O(mn) (where m is the number of edges,n is the number of vertices, O(m)=O(n2)). Compared to the existed algorithms,the proposed algorithm is effectiveness and correctness. |
| |
| Keywords: | DNA computing Tile self-assembly model maximum matching problem NP-complete problem parallel com-puting |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《电子学报》浏览原始摘要信息 |
| 点击此处可从《电子学报》下载免费的PDF全文 |
|
