![](/images/graphics-bg.png)
Solving Vertex Cover Problem Using DNA Tile Assembly Model
Joint Authors
Song, Tao
Shi, Xiaolong
Chen, Zhihua
Huang, Yufang
Source
Journal of Applied Mathematics
Issue
Vol. 2013, Issue 2013 (31 Dec. 2013), pp.1-7, 7 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2013-12-10
Country of Publication
Egypt
No. of Pages
7
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Chen, Zhihua& Song, Tao& Huang, Yufang& Shi, Xiaolong. 2013. Solving Vertex Cover Problem Using DNA Tile Assembly Model. Journal of Applied Mathematics،Vol. 2013, no. 2013, pp.1-7.
https://search.emarefa.net/detail/BIM-469725
Modern Language Association (MLA)
Chen, Zhihua…[et al.]. Solving Vertex Cover Problem Using DNA Tile Assembly Model. Journal of Applied Mathematics No. 2013 (2013), pp.1-7.
https://search.emarefa.net/detail/BIM-469725
American Medical Association (AMA)
Chen, Zhihua& Song, Tao& Huang, Yufang& Shi, Xiaolong. Solving Vertex Cover Problem Using DNA Tile Assembly Model. Journal of Applied Mathematics. 2013. Vol. 2013, no. 2013, pp.1-7.
https://search.emarefa.net/detail/BIM-469725
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-469725