图的顶点着色问题的DNA算法

• 作者: 许进 高琳
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: DNA计算 NP-完全问题 顶点着色问题 限制酶
• 年，卷（期）: 2003,（4）
• 所属期刊栏目: 学术论文
• 页码范围: 494-497
• 页数: 4页
• 分类号: TP18
• 字数: 2936字
• 语种: 中文
• DOI: 10.3321/j.issn:0372-2112.2003.04.003

摘要

图的顶点着色问题是指无向图中任意两个相邻顶点都分配到不同的颜色,这个问题是著名的NP-完全问题,没有非常有效的算法.但在1994年Adleman [1]首次提出用DNA计算解决NP-完全问题,设计出一种全新的计算模式-模拟生物分子DNA的结构并借助于分子生物技术进行计算,使得NP-完全问题的求解可能得到解决.本文首先提出了基于分子生物技术的图的顶点着色问题的DNA算法,算法的关键是对图中的顶点和顶点的颜色进行恰当的编码,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离,依据分子生物学的实验方法,本文提出的算法是有效和可行的;其次指出了该算法的优点、存在的问题及将来进一步的研究方向.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许进	华中科技大学系统科学研究所	117	2149	25.0	39.0
2	高琳	西安电子科技大学雷达信号处理国家重点实验室	43	810	16.0	28.0