基于闭环DNA计算的最大独立集问题的算法

Algorithm of Maximum Independent Set Problem Based on Closed Circle DNA Computing

提出闭环DNA计算模型及其基本生化实验,给出解决最大独立集问题的闭环DNA算法。在闭环DNA算法中,提出并实现了用删除实验直接构造所有最大独立集的构想,即通过多次删除实验使顶点集合逐步满足独立集的要求,最后达到最大独立集。该方法使得算法的设计简单明了。算法仅用到基本的删除实验,实现简捷、可靠。

This paper brings forward model of closed circle DNA computing and its basic bio-chemistry experiments. An algorithm with closed circle DNA of the maximum independent set problem is put forward. In the algorithm, an idea that all maximum independent sets are formed straightway by deleting experiment is put forward and realized, that condition of maximum independent is satisfied gradually by doing time after time delete experiments. Only using basic bio-chemistry experiment-delete experiment, the algorithm is simple and credible.