基于DNA计算的Hamilton图

数学季刊 ›› 2004, Vol. 19 ›› Issue (1): 79-83.

基于DNA计算的Hamilton图

Department of Mathematics and Physics, Anhui University of Science and Technology, Huainan 232001, China

收稿日期:2002-03-19 出版日期:2004-03-30 发布日期:2024-03-27
作者简介:ZHANG Jia-xiu(1969-),female,native of Huainan,Anhui,a lecture of Anhui University of Science and Technology,engages in graph theory,DNA computing ect..
基金资助:
Supported by the CNSF(60274026； 60174047； 30370356)； Supported by the Anhui Provinc’e Educational Committee Foundation(2003Kj098)；

Hamilton Graph Based on DNA Computing

Department of Mathematics and Physics, Anhui University of Science and Technology, Huainan 232001, China

Received:2002-03-19 Online:2004-03-30 Published:2024-03-27
About author:ZHANG Jia-xiu(1969-),female,native of Huainan,Anhui,a lecture of Anhui University of Science and Technology,engages in graph theory,DNA computing ect..
Supported by:
Supported by the CNSF(60274026； 60174047； 30370356)； Supported by the Anhui Provinc’e Educational Committee Foundation(2003Kj098)；

摘要/Abstract

摘要： DNA computing is a novel method for solving a class of intractable computational problem, in which the computing can grow exponentially with problem size. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. Hamilton Graph Problem has been solved by means of molecular biology techniques. A small graph was encoded in molecules of DNA, and the "operations" of the computation were performed with standard protocols and enzymes. This work represents further evidence for the ability of DNA computing to solve NP-complete search problems.

关键词: Hamilton , Graph, DNA , computing, NP-complete

Abstract: DNA computing is a novel method for solving a class of intractable computational problem, in which the computing can grow exponentially with problem size. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. Hamilton Graph Problem has been solved by means of molecular biology techniques. A small graph was encoded in molecules of DNA, and the "operations" of the computation were performed with standard protocols and enzymes. This work represents further evidence for the ability of DNA computing to solve NP-complete search problems.

Key words: Hamilton , Graph, DNA , computing, NP-complete

中图分类号:

O157.5

张家秀. 基于DNA计算的Hamilton图[J]. 数学季刊, 2004, 19(1): 79-83.

ZHANG Jia-xiu. Hamilton Graph Based on DNA Computing[J]. Chinese Quarterly Journal of Mathematics, 2004, 19(1): 79-83.

[1]	季琳星, 张科, 胡文军. 单层圆柱形网格图的独立多项式和Merrifield-Simmons指数[J]. 数学季刊, 2024, 39(4): 379-387.
[2]	席维鸽, 许涛. 非正则赋权有向图 A_a谱半径的上界[J]. 数学季刊, 2024, 39(2): 161-170.
[3]	杨瑞, 马燕菲. 富勒烯图的极大共振性[J]. 数学季刊, 2024, 39(1): 1-17.
[4]	刘树洋, 李峰. 强乘积图的最小强半径[J]. 数学季刊, 2024, 39(1): 68-72.
[5]	攸晓杰, 马海成, 张斌, 李雅兰. 两类四圈图的奇异性[J]. 数学季刊, 2023, 38(4): 349-359.
[6]	任世全, 王冲. 有向图的加权解析挠率[J]. 数学季刊, 2023, 38(1): 30-49.
[7]	张振坤, 叶稀琼. K 割宽临界树的构造[J]. 数学季刊, 2022, 37(4): 366-379.
[8]	张庆楠, 惠志昊, 杨雨, 王安. 哈林图的导出匹配可扩性[J]. 数学季刊, 2022, 37(4): 380-385.
[9]	赵秋兰, 原晋江. 关于3-正则哈密尔顿图的围长的一个注记[J]. 数学季刊, 2022, 37(4): 430-431.
[10]	张义冉, 王秀梅. 圈强迫的2-连通无爪三正则图的刻画#br# #br# [J]. 数学季刊, 2022, 37(4): 432-440.
[11]	夏伟皓, 石美, 肖明月, 蔡建生, 王纪辉. r-正则有向图的多数染色 [J]. 数学季刊, 2022, 37(2): 142-146.
[12]	白雨杰, 毋述斐. 一类三正则图的全友好指数集[J]. 数学季刊, 2021, 36(3): 221-234.
[13]	阴浩然, 李峰. 有向图强乘积的代数群性质[J]. 数学季刊, 2020, 35(4): 424-430.
[14]	陈丽娜, 谢炎涛. 关于H-cordial图和semi-H-cordial图的若干结论[J]. 数学季刊, 2019, 34(1): 52-56.
[15]	周后卿. 循环图的距离能量[J]. 数学季刊, 2018, 33(3): 233-239.