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

周旭; 周炎涛; 李肯立; 欧阳艾嘉; 潘果

doi:10.3969/j.issn.0372-2112.2015.02.009

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2025-07-16

- 基于Tile自组装模型的最大匹配问题算法研究
- Efficient Maximum Matching Problem Algorithms in the Tile Assembly Model
- 电子学报 2015年43卷第2期页码：262-268
- 作者机构：
  
  1. 嘉兴学院数理与信息工程学院,浙江,嘉兴,314001
  2. 湖南大学信息科学与工程学院,湖南,长沙,410082
  3. 湖南大学电气与信息工程学院,湖南,长沙,410082
  4. 嘉兴学院数理与信息工程学院,浙江,嘉兴,314001
  5. 湖南大学信息科学与工程学院,湖南,长沙,410082
  6. 湖南大学电气与信息工程学院,湖南,长沙,410082
- 作者简介：
- 基金信息：
  
  国家自然科学基金重点项目 (No.61133005);国家自然科学基金 (No.61173013,No.61202109);湖南省杰出青年基金 (No.12JJ1011);浙江省教育厅科研计划项目 (No.Y201226110);湖南省科技厅科技计划项目 (No.2013GK3082,No.2014GK3043);湖南省教育厅项目 (No.08D092,No.13C333)
- DOI：10.3969/j.issn.0372-2112.2015.02.009
  中图分类号： TP3
- 纸质出版：2015
- 稿件说明：
移动端阅览
周旭, 周炎涛, 李肯立, 等. 基于Tile自组装模型的最大匹配问题算法研究[J]. 电子学报, 2015,43(2):262-268.

ZHOU Xu, ZHOU Yan-tao, LI Ken-li, et al. Efficient Maximum Matching Problem Algorithms in the Tile Assembly Model[J]. Acta Electronica Sinica, 2015, 43(2): 262-268.
周旭, 周炎涛, 李肯立, 等. 基于Tile自组装模型的最大匹配问题算法研究[J]. 电子学报, 2015,43(2):262-268. DOI： 10.3969/j.issn.0372-2112.2015.02.009.

ZHOU Xu, ZHOU Yan-tao, LI Ken-li, et al. Efficient Maximum Matching Problem Algorithms in the Tile Assembly Model[J]. Acta Electronica Sinica, 2015, 43(2): 262-268. DOI： 10.3969/j.issn.0372-2112.2015.02.009.

摘要

Tile自组装模型作为一种重要的DNA计算模型

在解决NP问题时展现出了巨大优势.文中针对现有最大匹配问题DNA计算算法实验操作复杂

错误率高的缺点

提出了一种基于Tile自组装模型的最大匹配问题新算法.算法所需的Tile分子种类为

(

)

所需生物操作数为

(1)

计算时间为

(

)

计算空间复杂度为

(

)(其中

为边数

为顶点数

且

(

)).与现有的最大匹配问题DNA计算算法相比

本算法不仅可靠性更好

而且更具可操作性.

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

(

) types of tile molecular

its bio-operation is

(1)

the computing time is

(

) and space complexity is

(

) (where m is the number of edges

n is the number of vertices

(

)). Compared to the existed algorithms

the proposed algorithm is effectiveness and correctness.

关键词

Keywords

references

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

一种基于分治的三维匹配问题DNA计算算法

最大匹配问题的DNA表面计算模型

面向FPGA的布局与布线技术研究综述

DNA计算中的单模板编码方法改进研究

图3-着色问题的O链数DNA计算机算法