图3-着色问题的O(2n)链数DNA计算机算法

• 作者: 周旭 李肯立 许进
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: DNA超级计算 图3-着色问题 剪枝策略 NP完全问题
• 年，卷（期）: 2008,（11）
• 所属期刊栏目: 学术论文
• 页码范围: 2096-2101
• 页数: 6页
• 分类号: TP384
• 字数: 6383字
• 语种: 中文
• DOI: 10.3321/j.issn:0372-2112.2008.11.003

摘要

随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一,为减少图3-着色问题DNA计算机算法中的DNA链数,本文将Adleman-Lipton模型生物操作与粘贴模型解空间相结合的DNA计算模型进行扩展,通过设计顶点着色器、稀疏图/稠密图搜索器,提出一种用于求解图3-着色问题的DNA计算模型与算法.将本算法与同类算法对比分析表明:本算法在保持多项式操作时间的条件下,将求解n个顶点的图3-着色问题所需DNA分子链数从O(3n)减少至O(2n),改进了3-着色问题同类文献的研究结果.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李肯立	湖南大学计算机与通信学院	130	931	16.0	22.0
2	周旭	湖南大学计算机与通信学院	14	149	6.0	12.0
3	许进	华大科技大学分子生物计算机研究所	1	4	1.0	1.0