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)

LI Ken-li; ZHOU Xu; XU Jin

您当前的位置：

首页 >

文章列表页 >

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)

更新时间：2025-07-16

- 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)
- Acta Electronica Sinica Vol. 36, Issue 11, Pages: 2096-2101(2008)
- 作者机构：
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP384
- Published：2008
- 稿件说明：
移动端阅览
LI Ken-li, ZHOU Xu, XU Jin. 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)[J]. Acta Electronica Sinica, 2008, 36(11): 2096-2101.
DOI：

LI Ken-li, ZHOU Xu, XU Jin. 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)[J]. Acta Electronica Sinica, 2008, 36(11): 2096-2101. DOI：

摘要

随着DNA计算的不断发展

如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一.为减少图3-着色问题DNA计算机算法中的DNA链数

本文将Adleman-Lipton模型生物操作与粘贴模型解空间相结合的DNA计算模型进行扩展

通过设计顶点着色器、稀疏图/稠密图搜索器

提出一种用于求解图3-着色问题的DNA计算模型与算法.将本算法与同类算法对比分析表明:本算法在保持多项式操作时间的条件下

将求解

个顶点的图3-着色问题所需DNA分子链数从

O(3

)减少至O(2

)

改进了3-着色问题同类文献的研究结果.

Abstract

The DNA volume which increases in a pure exponentially with the scale of the problem has become the bottleneck problem.So how to decrease the volume in DNA computers is of a great significance in the research of DNA computing.For the objective to decrease the DNA volume of the 3-colorable problem

an improved DNA computing model basing on the biological operations in the Adleman-Lipton model and the solution space of stickers in the sticker-based model is introduced.Furthermore

a new DNA algorithm where new algorithms of Vertex Shader

Sparse Parallel Searcher and Dense Parallel Searcher

are developed to solve the 3-colorable problem.The proposed algorithm can solve the 3-colorable problem by using the

O(2

)

shorter DNA strands on the condition of not varying the time complexity

as compared by far the best molecular algorithm for it in which

O(3

)

DNA strands is used.

关键词

Keywords

references

Views

1268

下载量

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

Efficient Maximum Matching Problem Algorithms in the Tile Assembly Model

Related Author

ZHOU Xu

LI Ken-li

YUE Guang-xue

YANG Zhi-bang

ZHOU Xu

ZHOU Yan-tao

LI Ken-li

OUYANG Ai-jia

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

College of Mathematics and Information Engineering, Jiaxing University

⁰