Algorithm of Solving the Maximum Edges Independent Set Problem Based on DNA Molecules Computation

作者：Wang, Zhaocai; Huang, Wei^*; Ye, Chaorong; Zhang, Yiming

来源：Journal of Computational and Theoretical Nanoscience, 2014, 11(4): 961-963.

DOI：10.1166/jctn.2014.3450

• DNA Computation
• The Maximum Edges Independent Set Problem
• Adleman-Lipton Model
• NP-Complete Problem

The maximum edges independent set (MEIS) problem is a vitally important NP-complete problem in graph theory, having numerous real life applications. In this paper, we present a DNA algorithm for solving the MEIS problem with DNA molecular operations. We extend the application of DNA molecular operations and simultaneity simplify the complexity of the computation.

• 出版日期2014-4
• 单位上海海洋大学; 贵阳学院; 盐城工学院