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

摘要：

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

关键词：DNA超级计算、最大团问题、剪枝技术、NP完全问题

所属期刊栏目：31

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金60603053,90715029

在线出版日期：2009-03-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：2173-2181