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

• 作者: 周旭 周炎涛 李肯立 欧阳艾嘉 潘果
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: DNA计算 Tile自组装模型 最大匹配问题 NP完全问题 并行计算
• 年，卷（期）: 2015,（2）
• 页码范围: 262-268
• 页数: 7页
• 分类号: TP3
• 字数: 4579字
• 语种: 中文
• DOI: 10.3969/j.issn.0372-2112.2015.02.009

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周炎涛	湖南大学信息科学与工程学院	42	618	13.0	24.0
5	李肯立	湖南大学信息科学与工程学院	130	931	16.0	22.0
6	周旭	嘉兴学院数理与信息工程学院	18	115	7.0	10.0
8	欧阳艾嘉	湖南大学信息科学与工程学院	14	81	6.0	8.0
11	潘果	湖南大学信息科学与工程学院	9	51	4.0	6.0