| 一种改进的最大团问题DNA计算机算法(英文) |
| |
| 引用本文： | 李肯立,周旭,邹舒婷.一种改进的最大团问题DNA计算机算法(英文)[J].计算机学报,2008,31(12). |
| |
| 作者姓名： | 李肯立 周旭 邹舒婷 |
| |
| 作者单位： | 1. 湖南大学计算机与通信学院,长沙,410082;华中科技大学分子生物计算机研究所,武汉,430074
2. 湖南大学计算机与通信学院,长沙,410082 |
| |
| 基金项目： | 国家自然科学基金
|
| |
| 摘 要： | 随着DNA计算的不断发展，如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一．将图灵机中的剪枝算法设计技术应用于最大团问题的DNA计算中，提出一种最大团问题的新DNA计算机算法．算法由顶点度数搜索器、团生成器、稀疏图与稠密图并行搜索器以及最大团搜索器组成．与已有文献同类算法的对比分析表明：文中算法在保持多项式操作时间的条件下，将求解n个顶点的最大团问题所需DNA分子链数从现有文献的O（2^n）减少至O（√3^n），同时文中算法还具有高效的空间利用率及容错能力的优点．
|
| 关 键 词： | DNA超级计算 最大团问题 剪枝技术 NP完全问题 |
Improved Volume Molecular Solutions for the Maximum Clique Problem on DNA-Based Supercomputing |
| |
| LI Ken-Li,ZHOU Xu,ZOU Shu-Ting.Improved Volume Molecular Solutions for the Maximum Clique Problem on DNA-Based Supercomputing[J].Chinese Journal of Computers,2008,31(12). |
| |
| Authors: | LI Ken-Li ZHOU Xu ZOU Shu-Ting |
| |
| Affiliation: | LI Ken-Li1),2)ZHOU Xu1)ZOU Shu-Ting1)1)(School of Computer , Communications,Hunan University,Changsha 410082)2)(Institute of Biomolecular Computer,Huazhong University of Science , Technology,Wuhan 430074) |
| |
| Abstract: | 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 ma... |
| |
| Keywords: | DNA-based supercomputing maximum clique problem pruning strategy NP-com-plete problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
