Applying Surface-Based DNA Computing for Solving the Dominating Set Problem  

作　　者：Hassan Taghipour Mahdi Rezaei Heydar Ali Esmaili 

机构地区：[1]Department of pathology, Tabriz University of medical sciences, Tabriz, Iran [2]Department of Theoretical Physics and Astrophysics, Tabriz University, Tabriz, 51664, Iran

出　　处：《American Journal of Molecular Biology》2012年第3期286-290,共5页美国分子生物学期刊（英文）

摘　　要：The surface-based DNA computing is one of the methods of DNA computing which uses DNA strands immobilized on a solid surface. In this paper, we applied surface-based DNA computing for solving the dominating set problem. At first step, surface-based DNA solution space was constructed by using appropriate DNA strands. Then, by application of a DNA parallel algorithm, dominating set problem was resolved in polynomial time.The surface-based DNA computing is one of the methods of DNA computing which uses DNA strands immobilized on a solid surface. In this paper, we applied surface-based DNA computing for solving the dominating set problem. At first step, surface-based DNA solution space was constructed by using appropriate DNA strands. Then, by application of a DNA parallel algorithm, dominating set problem was resolved in polynomial time.

关 键 词：Parallel Computing Surface-Based DNA Computers Dominating Set PROBLEM NP-COMPLETE PROBLEM 

分 类 号：O1[理学—数学]