Solving the independent set problem by sticker based DNA computers

• 作者: Ahad Taghipour Hassan Taghipour Heydar Ali Esmaili Mahdi Rezaei
• 来源期刊: 美国分子生物学期刊(英文)
• 学科: 数学
• 关键词: Parallel COMPUTING Sticker BASED DNA COMPUTERS INDEPENDENT Set PROBLEM NP-COMPLETE PROBLEM
• 年，卷（期）: 2012,（2）
• 页码范围: 153-158
• 页数: 6页
• 分类号: O1

摘要

In this paper, the sticker based DNA computing was used for solving the independent set problem. At first, solution space was constructed by using appropriate DNA memory complexes. We defined a new operation called “divide” and applied it in construction of solution space. Then, by application of a sticker based parallel algorithm using biological operations, independent set problem was resolved in polynomial time.