Solving Vertex Cover Problem Using DNA Tile Assembly Model

المؤلفون المشاركون

Song, Tao
Shi, Xiaolong
Chen, Zhihua
Huang, Yufang

المصدر

Journal of Applied Mathematics

العدد

المجلد 2013، العدد 2013 (31 ديسمبر/كانون الأول 2013)، ص ص. 1-7، 7ص.

الناشر

Hindawi Publishing Corporation

تاريخ النشر

2013-12-10

دولة النشر

مصر

عدد الصفحات

7

التخصصات الرئيسية

الرياضيات

الملخص 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.

نمط استشهاد جمعية علماء النفس الأمريكية (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

نمط استشهاد الجمعية الأمريكية للغات الحديثة (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

نمط استشهاد الجمعية الطبية الأمريكية (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

نوع البيانات

مقالات

لغة النص

الإنجليزية

الملاحظات

Includes bibliographical references

رقم السجل

BIM-469725