求解最大完全子图的一种DNA算法

江汉大学学报（自然科学版） ›› 2012, Vol. 40 ›› Issue (1): 20-23.

求解最大完全子图的一种DNA算法

董敏，汤建钢

伊犁师范学院数学与统计学院，新疆伊宁835000

收稿日期:2011-05-09 出版日期:2012-02-20 发布日期:2013-11-07
作者简介:董敏单位1984—)，男，硕士生，研究方向:DNA计算。
基金资助:
新疆维吾尔自治区自然科学基金资助项目单位2011211A051

The DNA Algorithm of Solving Maximum Complete Subgraph

DONG Min,TANG Jian－gang

College of Mathematics and Statistics,YILI Normal University,Yining 835000,Xinjiang,China

Received:2011-05-09 Online:2012-02-20 Published:2013-11-07

摘要/Abstract

摘要： 最大完全子图是图论中一个重要的问题。粘贴和删除模型是DNA计算的两个基本计算模型。利用改进的粘贴和删除模型给出求解最大完全子图的DNA算法。

关键词: DNA计算, 粘贴模型, 删除模型, 最大完全子图

Abstract: Maximum complete subgraph is an important problem in graph theory. Sticker model and deletion model are two basic kinds of DNA computing models. This paper proposes a DNA algrothm of solving maximum complete subgraph based on sticker model and deletion model.

Key words: DNA computing, sticker model, deletion model, maximum complete subgraph

中图分类号:

TP301.6

董敏，汤建钢. 求解最大完全子图的一种DNA算法[J]. 江汉大学学报（自然科学版）, 2012, 40(1): 20-23.

DONG Min,TANG Jian－gang. The DNA Algorithm of Solving Maximum Complete Subgraph[J]. Journal of Jianghan University(Natural Science Edition), 2012, 40(1): 20-23.

参考文献

[1]Adleman L M.Molecular computation of solution to combinatorial problems problems[J].Science,1994, 2661021－1023.
［2]Lipton R.Using DNA to solve SAT[EB／OL].1995.
［3]Ouyang Q,Kaplan P D,Liu S,et al.DNA solution of the maximal clique problem[J].Science,1997,278单位 5337)446－449.
［4]Wang L, Liu Q, Frutos A G, et al.Surface－based on DNA computing operationsDESTROY and READOUT[J].Biosystems,1999,52单位 1－3)189－191.
［5]Ibrahim Z,Tsuboi Y.Molecular computation approach to compete Dijkstra’s algorithm[C]//5th Asian Control Conference,200422.
［6]Gao L,Xu J.DNA Solution of vertex cover problem basedon stieker model[J].Chinese Journal of Electronies,2002,Ⅱ单位 2)280－284.
［7]董敏,汤建钢.基于粘贴和删除系统求解旅行商问题的DNA算法[J].江汉大学学报自然科学版,2011, 39单位 4)7-10.
［8]徐进.DNA计算一种新的计算模式[M].王淑栋,潘林强,等译.北京清华大学出版社,2004.
［9]许进,董亚非,魏小鹏.粘贴DNA计算机模型单位 I)理论[J].科学通报,2004,49单位 3)568－573.
［10]许进,李三平,董亚非,等.粘贴DNA计算机模型单位 11)应用[J].科学通报,2004,49单位 4)299－307.
［11]West D B.Introduction to graph theory[M].2rd.北京机械工业出版社,2006.
［12]Andrasfai B.图论导引[M].北京高等教育出版社,1985.
［13]邦迪J A,默蒂U S R.图论及其应用[M].北京科学技术出版社,1985.
［14]马莹.图论中的DNA计算[J].计算机与数字工程,2007,35单位 8)100－102.
［15]王淑栋.图的最小顶点覆盖问题的质粒DNA计算模型[J].Huazhong Univ of Sci ＆ TechNature Science Edition,2004,3259－61.
［16]王淑栋.四类DNA计算模型中一些理论与应用的研究[D].武汉华中科技大学,200469－73.
［17]董亚非,张家秀,殷志祥,等.最小顶点覆盖问题的改进粘贴模型[J].电子与信息学报,2005,27单位 4)556-560.
［18]Peter L.形式语言与自动机导论[M].孙家骕,译.北京机械工业出版社,2005.
［19]Lipton R J.DNA solution of hard computation problems[J].Science,1995,268单位 4)542－545.

[1]	聂晓艳，耿俊，汤建钢. 基于粘贴系统求解无向图最短路径问题的DNA计算模型[J]. 江汉大学学报（自然科学版）, 2012, 40(5): 5-8.
[2]	董敏, 汤建钢. 基于粘贴和删除系统求解旅行商问题的DNA算法[J]. 江汉大学学报（自然科学版）, 2011, 39(4): 7-10.