| ¡¡ | Chinese Journal of Computers Full Text |
| Title | Improved Volume Molecular Solutions for the Maximum Clique Problem on DNA-Based Supercomputing |
| Authors | LI Ken-Li1),2) ZHOU Xu1) ZOU Shu-Ting1) |
| Address | 1)(School of Computer and Communications, Hunan University, Changsha 410082) 2)(Institute of Biomolecular Computer, Huazhong University of Science and Technology, Wuhan 430074) |
| Year | 2008 |
| Issue | No.12(2173¡ª2181) |
| Abstract & Background | 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 maximum number required is O(3n) on the condition of not varying the time complexity where n is the number of the vertex in a graph, while O(2n) 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. Keywords DNA-based supercomputing; maximum clique problem; pruning strategy; NP-complete problem |