TITLE:
Applying Surface-Based DNA Computing for Solving the Dominating Set Problem
AUTHORS:
Hassan Taghipour, Mahdi Rezaei, Heydar Ali Esmaili
KEYWORDS:
Parallel Computing; Surface-Based DNA Computers; Dominating Set Problem; NP-Complete Problem
JOURNAL NAME:
American Journal of Molecular Biology,
Vol.2 No.3,
July
16,
2012
ABSTRACT: 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.