文献类型：期刊文献

中文题名：最大匹配问题的粘贴DNA算法

英文题名：DNA Algorithm for Maximum Matching Problem Based on Sticker Computation Model

作者：吴雪[1];宋晨阳[2];张楠[1];朱煜[1];陈志华[1]

机构：[1]华东理工大学信息科学与工程学院,上海200237;[2]上海通用识别技术研究所,上海201112

年份：2013

卷号：40

期号：12

起止页码：127

中文期刊名：计算机科学

外文期刊名：Computer Science

收录：CSTPCD;;北大核心:【北大核心2011】；CSCD:【CSCD2013_2014】；

基金：国家自然科学基金(61370174);中央高校基本科研业务费专项资金(WH1114030)资助

语种：中文

中文关键词：DNA计算;最大匹配;粘贴模型

外文关键词：DNA computing, Maximum matching, Sticker model

摘要：最大匹配问题(MMP)是图论中经典的组合优化问题。针对此问题提出了基于DNA粘贴计算模型的求解算法,阐述了该算法如何利用DNA链构建最大匹配问题的初始编码,说明了应用粘贴计算模型寻求最终解的生物操作过程,同时分析了此DNA并行算法的计算复杂度,最后给出了该算法的计算机模拟仿真结果和应用实例,得到了所给问题的最大匹配解,并对算法的可行性进行了验证和总结。
This paper the DNA solution of the maximum matching problem（MMP） based on sticker computation model was presented,showed how to use DNA strands to construct solution space of mole-cules for the maximum matching problem and how to apply the biological operations of sticker model to solve the problem from the solution space of mole- cules,at the same time analysed of the computational complexity for DNA parallel algorithms. Finally, the computer program was given to simulate this algorithm and the solutions of MMP for all examples were also found, and the feasibili-ty of the algorithm was validated and summarized.