最大匹配问题的DNA表面计算模型

A Surface-Based DNA Algorithm for Maximal Matching Problem

本文给出了一个最大匹配问题的DNA表面计算模型 ,我们在表面上逐步生成解空间的同时 ,利用酶切技术删除所产生的“不可行解” ,从而大大减少了最终生成的解空间 .最后 ,我们还研究了边的排列顺序对解空间的生成过程的影响 .结果表明 ,通过对图中的边进行合理的编排也能减小不可行解的生成 .

This paper first proposes a DNA algorithm based on surface for the maximal matching problem.The main idea is to generate the possible solution space step by step in the solid surface,and at the same time these fault solutions are deleted through the digestion process of restriction enzymes.Finally the influence of the edge order on the solution generating process is discussed.Our results show that the solution space can be efficiently reduced by a reasonable arrangement of the order of edges.