%0 Journal Article
%T 基于Tile自组装模型的最大匹配问题算法研究
%A 周旭
%A 周炎涛
%A 李肯立
%A 欧阳艾嘉
%A 潘果
%J 电子学报
%P 262-268
%D 2015
%R 10.3969/j.issn.0372-2112.2015.02.009
%X Tile自组装模型作为一种重要的DNA计算模型,在解决NP问题时展现出了巨大优势.文中针对现有最大匹配问题DNA计算算法实验操作复杂,错误率高的缺点,提出了一种基于Tile自组装模型的最大匹配问题新算法.算法所需的Tile分子种类为O(mn),所需生物操作数为O(1),计算时间为O(m),计算空间复杂度为O(mn)(其中m为边数,n为顶点数,且O(m)=O(n2)).与现有的最大匹配问题DNA计算算法相比,本算法不仅可靠性更好,而且更具可操作性.
%K DNA计算
%K Tile自组装模型
%K 最大匹配问题
%K NP完全问题
%K 并行计算
%U http://www.ejournal.org.cn/CN/abstract/abstract8800.shtml