Efficient Maximum Matching Problem Algorithms in the Tile Assembly Model

ZHOU Xu; ZHOU Yan-tao; LI Ken-li; OUYANG Ai-jia; PAN Guo

doi:10.3969/j.issn.0372-2112.2015.02.009

您当前的位置：

首页 >

文章列表页 >

Efficient Maximum Matching Problem Algorithms in the Tile Assembly Model

更新时间：2025-07-16

- Efficient Maximum Matching Problem Algorithms in the Tile Assembly Model
- Acta Electronica Sinica Vol. 43, Issue 2, Pages: 262-268(2015)
- 作者机构：
  
  1. 嘉兴学院数理与信息工程学院,浙江,嘉兴,314001
  2. 湖南大学信息科学与工程学院,湖南,长沙,410082
  3. 湖南大学电气与信息工程学院,湖南,长沙,410082
  4. 嘉兴学院数理与信息工程学院,浙江,嘉兴,314001
  5. 湖南大学信息科学与工程学院,湖南,长沙,410082
  6. 湖南大学电气与信息工程学院,湖南,长沙,410082
- 作者简介：
- 基金信息：
  
  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)
- DOI：10.3969/j.issn.0372-2112.2015.02.009
  CLC： TP3
- Published：2015
- 稿件说明：
移动端阅览
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：

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

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A New DNA Computing's Algorithm for 3-Dimensional Matching Problem Based on Divide and Conquer Strategy

A Surface-Based DNA Algorithm for Maximal Matching Problem

Review on Technology of Placement and Routing for the FPGA

Improving the Single Template Method in DNA Computing

An O Volume Molecular Solutions for the 3-Colorable Problem on DNA-Based Supercomputing ( 1.School of Computer and communications,Hunan University,Changsha,Hunan 410082,China; 2.Institute of Biomolecular Computer,Huazhong University of Science and Technology,Wuhan,Hubei 430074,China)

Related Author

ZHOU Xu

LI Ken-li

YUE Guang-xue

YANG Zhi-bang

LIU Wen-bin

GAO Lin

WANG Shu-dong

LIU Xiang-rong

Related Institution

College of Mathematics and Information Engineering,Jiaxing University

School of Computer and Communications,Hunan University

College of Mathematics and Information EngineeringJiaxing UniversityJiaxingZhejiang 314001China

School of Computer and CommunicationsHunan UniversityChangshaHunan 410082China

National Key Lab.of Radar Signal ProcessingXidian Univ.Xi'anShanxi 710071China

⁰