Fast parallel molecular solution to the dominating-set problem on massively parallel bio-computing

✍ Scribed by Minyi Guo; Michael (Shan-Hui) Ho; Weng-Long Chang

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 254 KB
• Volume: 30
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/j.parco.2004.07.014

✦ Synopsis

This paper shows how to use DNA strands to construct solution space of molecules for the dominating-set problem and how to apply biological operations to solve the problem from the solution space of molecules. In order to achieve this, we have proposed some DNA based parallel algorithms using the operations in Adleman-Lipton model, together with the analysis of the computational complexity for DNA parallel algorithms.