一种改进的最大团问题DNA计算机算法

• 作者: 周旭 李肯立 邹舒婷
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: DNA超级计算 最大团问题 剪枝技术 NP完全问题
• 年，卷（期）: 2008,（12）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 2173-2181
• 页数: 9页
• 分类号: TP301
• 字数: 2977字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2008.12.015

摘要

随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一.将图灵机中的剪枝算法设计技术应用于最大团问题的DNA计算中,提出一种最大团问题的新DNA计算机算法.算法由顶点度数搜索器、团生成器、稀疏图与稠密图并行搜索器以及最大团搜索器组成.与已有文献同类算法的对比分析表明:文中算法在保持多项式操作时间的条件下,将求解 n 个顶点的最大团问题所需DNA分子链数从现有文献的O(2n)减少至O(3n),同时文中算法还具有高效的空间利用率及容错能力的优点.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李肯立	湖南大学计算机与通信学院	130	931	16.0	22.0
5	周旭	湖南大学计算机与通信学院	14	149	6.0	12.0
6	邹舒婷	湖南大学计算机与通信学院	1	16	1.0	1.0