FAST PARALLEL DNA ALGORITHM BASED ON ADLEMAN-LIPTON MODEL: THE INDEPENDENT DOMINATING SET PROBLEM

The independent dominating set problem is a classical optimization problem and has been shown to be NP-Complete. This study finds a molecular computing model to solve the independent dominating set problem, based on Adleman-Lipton model. It proves how to apply stickers in the sticker based model to construct the DNA solution space of the independent dominating set problem and how to apply DNA operations in the Adleman-Lipton model to solve that problem from the solution space of stickers. The time complexity of the proposed computational model is O(n + 2m)and to verify this model, a small independent dominating set problem was solved. This proves the capacity of molecular computing for solving the complex independent dominating set problem.