For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Fast Parallel Solution for Set-Packing and Clique Problems by DNA-Based Computing
Michael (Shan-Hui) HO Weng-Long CHANG Minyi GUO Laurence T. YANG
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2004/07/01
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Hardware/Software Support for High Performance Scientific and Engineering Computing)
Category: Scientific and Engineering Computing with Applications
biological computing, molecular computing, DNA-based computing,
Full Text: PDF(978.7KB)
>>Buy this Article
This paper shows how to use sticker to construct solution space of DNA for the library sequences in the set-packing problem and the clique problem. Then, with biological operations, we propose DNA-based algorithms to remove illegal solutions and to find legal solutions for the set-packing and clique problems from the solution space of sticker. Any NP-complete problem in Cook's Theorem can be reduced and solved by the proposed DNA-based computing approach if its size is equal to or less than that of the set-packing problem. Otherwise, Cook's Theorem is incorrect on DNA-based computing and a new DNA algorithm should be developed from the characteristics of the NP-complete problem. Finally, the result to DNA simulation is given.