Solving Vertex Cover Problem Using DNA Tile Assembly Model

Zhihua Chen, Tao Song, Yufang Huang and Xiaolong Shi

Journal of Applied Mathematics, 2013, vol. 2013, issue 1

Abstract: DNA tile assembly models are a class of mathematically distributed and parallel biocomputing models in DNA tiles. In previous works, tile assembly models have been proved be Turing‐universal; that is, the system can do what Turing machine can do. In this paper, we use tile systems to solve computational hard problem. Mathematically, we construct three tile subsystems, which can be combined together to solve vertex cover problem. As a result, each of the proposed tile subsystems consists of Θ(1) types of tiles, and the assembly process is executed in a parallel way (like DNA’s biological function in cells); thus the systems can generate the solution of the problem in linear time with respect to the size of the graph.

Date: 2013
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1155/2013/407816

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:jnljam:v:2013:y:2013:i:1:n:407816

Access Statistics for this article

More articles in Journal of Applied Mathematics from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().