期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于剪接系统的有向哈密顿路问题分析 被引量：2

Analysis for Directed Hamilton Path Problems Based on Splicing Systems
下载PDF
导出
摘要 　首先给出了剪接系统模拟有向哈密顿路问题的思想;然后通过此剪接系统所产生语言的性质对有向哈密顿路问题进行分析,给出了有向图存在哈密顿路的充要条件.在我们的构造中,模拟问题的剪接系统至多运行n-2步,其中n是模拟问题的规模. The ideas of simulating directed Hamilton path problems by splicing systems are showed, then some properties of directed graphs are presented based on the analysis of directed Hamilton path problems according to the properties of languages generated by the splicing systems. In our construction, the splicing systems simulating problems run at most n-2 steps, where n is the size of problems.
作者 王淑栋 许进 刘文斌
机构地区 山东科技大学信息科学与工程学院 华中科技大学控制科学与工程系
出处 《电子学报》 EI CAS CSCD 北大核心 2005年第5期774-777,共4页 Acta Electronica Sinica
基金 国家自然科学基金(No.60174047 No.60274026 No.60403002)
关键词 DNA计算 剪接系统 有向哈密顿路问题 Calculations Computational complexity Computer programming languages Computer simulation Construction Graph theory Theorem proving
分类号 TP18 [自动化与计算机技术—控制理论与控制工程]
  • 相关文献

参考文献9

  • 1T Head.Formal language theory and DNA:an analysis of the generative capacity of specific recombinant behaviors[J].Bull.Math.Biol,1987,49:737-759.
  • 2T Head.Splicing schemes and DNA[J].Nanobiology,1992,1:335-342.
  • 3E Csuhaj-Varju,L Freund,L Kari,Gh Pun.DNA computing based on splicing:universality results[A].Proceedings of 1st Annual Pacific Symposium on Biocomputing[C].Hawaii,Jan.1996.
  • 4Gh Paun,A Salomaa.DNA computing based on the splicing operation[J].Math.Japonica,1996,43(3):607-632.
  • 5R Freund,L Kari,Gh Pun.DNA computing based on splicing:The existence of universal computers[J].Theory of Computing Systems,1999,32:69-112.
  • 6Y Benenson,T Paz-Elizur,et al.Programmable and autonomous computing machine made of biomolecules[J].Nature,2001,414(22):430-434.
  • 7Katrin Erk.Simulating boolean circuits by finite splicing[A].In Proceedings of the Congress on Evolutionary Computation (CEC'99)[C].Washington D.C,USA,July 6-9,1999.
  • 8L M Adleman.Molecular computation of solution to combinatorial problems[J].Science 1994,266:1021-1024.
  • 9J A Bondy,U S R Murty.Graph Theory with Application[M].The Macmillan Press Ltd,1976.

同被引文献16

  • 1陈治平,李小龙,王雷,林亚平,蔡立军.最佳匹配问题的DNA表面计算模型[J].计算机研究与发展,2005,42(7):1241-1246. 被引量：7
  • 2Adleman L M.Molecular computation of solutions to combinatorial problems[J].Science, 1994,266:1021-1024.
  • 3Lipton R J.Speeding up computations via molecular biology[R]. Princeton University, 1994.
  • 4Lipton R J.DNA solution of hard computational problems[J].Science, 1995,268 : 542-545.
  • 5Ouyang Q,Kaplan P D,Liu S,et al.Solution of the maximal clique problem[J].Science, 1997,278 ( 17 ) : 446-449.
  • 6Head T,Rozenberg G,Bladergroen R S,et al.Computing with DNA by operating on plasmids[J].Biosystems, 2000,57 : 87-93.
  • 7Braieh R S,Chelyapov N,Johnson C.Solution of a 20-variable 3- SAT problem on a DNA computer[J].Seienee,2002,296(19):499- 502.
  • 8Liu Q,Wang L,Frutos A G,et al.DNA computing on surface[J]. Nature, 2000,403 ( 13 ) : 175-179.
  • 9Wu H.An improved surface-based method for DNA computation[J]. Biosystems, 2001,59 : 1-5.
  • 10Martinez-Perez I M,Zimmermann K H.Parallel bioinspired algorithms for NP complete graph problems[J].Joumal of Parallel and Distributed Computing, 2009,69: 221-229.

引证文献2

二级引证文献3

电子学报
2005年 第5期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部