电子学报 ›› 2015, Vol. 43 ›› Issue (2): 262-268.DOI: 10.3969/j.issn.0372-2112.2015.02.009

• 学术论文 • 上一篇    下一篇

基于Tile自组装模型的最大匹配问题算法研究

周旭1,2, 周炎涛2,3, 李肯立2, 欧阳艾嘉2, 潘果2   

  1. 1. 嘉兴学院数理与信息工程学院, 浙江嘉兴 314001;
    2. 湖南大学信息科学与工程学院, 湖南长沙 410082;
    3. 湖南大学电气与信息工程学院, 湖南长沙 410082
  • 收稿日期:2013-09-18 修回日期:2014-04-22 出版日期:2015-02-25
    • 通讯作者:
    • 周炎涛
    • 作者简介:
    • 周 旭 女,1983年生于江苏宿迁,湖南大学博士研究生,研究方向为DNA计算和并行计算. E-mail:zhouxu2006@126.com
    • 基金资助:
    • 国家自然科学基金重点项目 (No.61133005); 国家自然科学基金 (No.61173013,No.61202109); 湖南省杰出青年基金 (No.12JJ1011); 浙江省教育厅科研计划项目 (No.Y201226110); 湖南省科技厅科技计划项目 (No.2013GK3082,No.2014GK3043); 湖南省教育厅项目 (No.08D092,No.13C333)

Efficient Maximum Matching Problem Algorithms in the Tile Assembly Model

ZHOU Xu1,2, ZHOU Yan-tao2,3, LI Ken-li2, OUYANG Ai-jia2, PAN Guo2   

  1. 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
  • Received:2013-09-18 Revised:2014-04-22 Online:2015-02-25 Published:2015-02-25
    • Supported by:
    • Key Program of National Natural Science Foundation of China (No.61133005); National Natural Science Foundation of China (No.61173013, No.61202109); Excellent Youth Foundation of Hunan Province (No.12JJ1011); Project of Scientific Research Project of Zhejiang Education Department (No.Y201226110); Science and Technology Project of Department of Science and Technology of Hunan Provicne (No.2013GK3082, No.2014GK3043); Program of Hunan Education Department (No.08D092, No.13C333)

摘要:

Tile自组装模型作为一种重要的DNA计算模型,在解决NP问题时展现出了巨大优势.文中针对现有最大匹配问题DNA计算算法实验操作复杂,错误率高的缺点,提出了一种基于Tile自组装模型的最大匹配问题新算法.算法所需的Tile分子种类为O(mn),所需生物操作数为O(1),计算时间为O(m),计算空间复杂度为O(mn)(其中m为边数,n为顶点数,且O(m)=O(n2)).与现有的最大匹配问题DNA计算算法相比,本算法不仅可靠性更好,而且更具可操作性.

关键词: DNA计算, Tile自组装模型, 最大匹配问题, NP完全问题, 并行计算

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.

Key words: DNA computing, Tile self-assembly model, maximum matching problem, NP-complete problem, parallel computing

中图分类号: