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

• 作者: Hassan Taghipour Heydar Ali Esmaili Mahdi Rezaei
• 来源期刊: 美国分子生物学期刊(英文)
• 学科: 数学
• 关键词: Parallel Computing Surface-Based DNA Computers Dominating Set PROBLEM NP-COMPLETE PROBLEM
• 年，卷（期）: 2012,（3）
• 页码范围: 286-290
• 页数: 5页
• 分类号: O1

摘要

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.