一种基于贴纸模型的最大团问题新解决方案。
A new solution for maximal clique problem based sticker model.
作者信息
Darehmiraki Majid
机构信息
University of Birjand, Factuality of Sciences, Department of Mathematics, Birjand, South Khorasan, Iran.
出版信息
Biosystems. 2009 Feb;95(2):145-9. doi: 10.1016/j.biosystems.2008.09.007. Epub 2008 Oct 17.
In this paper, we use stickers to construct a solution space of DNA for the maximal clique problem (MCP). Simultaneously, we also apply the DNA operation in the sticker-based model to develop a DNA algorithm. The results of the proposed algorithm show that the MCP is resolved with biological operations in the sticker-based model for the solution space of the sticker. Moreover, this work presents clear evidence of the ability of DNA computing to solve the NP-complete problem. The potential of DNA computing for the MCP is promising given the operational time complexity of O(nxk).
在本文中，我们使用贴纸构建用于最大团问题（MCP）的DNA解空间。同时，我们还在基于贴纸的模型中应用DNA操作来开发一种DNA算法。所提算法的结果表明，在基于贴纸的模型中，通过生物学操作可解决贴纸解空间的最大团问题。此外，这项工作清楚地证明了DNA计算解决NP完全问题的能力。鉴于其O(nxk)的操作时间复杂度，DNA计算解决最大团问题的潜力很可观。
Zotero 插件