一种改进的最大团问题DNA计算机算法(英文)  

Improved Volume Molecular Solutions for the Maximum Clique Problem on DNA-Based Supercomputing

作　　者：李肯立[1,2] 周旭[1] 邹舒婷[1] 

机构地区：[1]湖南大学计算机与通信学院,长沙410082 [2]华中科技大学分子生物计算机研究所,武汉430074

出　　处：《计算机学报》2008年第12期2173-2181,共9页Chinese Journal of Computers

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

摘　　要：随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一.将图灵机中的剪枝算法设计技术应用于最大团问题的DNA计算中,提出一种最大团问题的新DNA计算机算法.算法由顶点度数搜索器、团生成器、稀疏图与稠密图并行搜索器以及最大团搜索器组成.与已有文献同类算法的对比分析表明:文中算法在保持多项式操作时间的条件下,将求解n个顶点的最大团问题所需DNA分子链数从现有文献的O(2n)减少至O(3^(1/2)~n),同时文中算法还具有高效的空间利用率及容错能力的优点.How to decrease the volume in DNA computers is of a great significance in the research of DNA computing. For the objective to decrease the DNA volume of the maximum clique problem which is a famous NP-complete problem, the pruning strategy is introduced into the DNA supercomputing and a new DNA algorithm is proposed. The new algorithm consists of a Degree Searcher, a Clique Generator, a Dense Parallel Searcher, a Sparse Parallel Searcher and a Maximum Clique Searcher. In a computer simulation, the DNA strands of maximum number required is O（√3^n） on the condition of not varying the time complexity where n is the number of the vertex in a graph, while O（2^n） DNA strands are needed in present molecular algorithms for the maximum clique problems. Furthermore, this algorithm is highly space-efficient and error-tolerant compared to conventional brute-force searching.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]