The Application of DNA Self-Assembly Model for Bin Packing Problem

Yanfeng Wang, Xuewen Bai, Donghui Wei, Weili Lu and Guangzhao Cui
Additional contact information
Yanfeng Wang: Zhengzhou University of Light Industry, China
Xuewen Bai: Zhengzhou University of Light Industry, China
Donghui Wei: Zhengzhou University of Light Industry, China
Weili Lu: Zhengzhou University of Light Industry, China
Guangzhao Cui: Zhengzhou University of Light Industry, China

International Journal of Natural Computing Research (IJNCR), 2012, vol. 3, issue 1, 1-15

Abstract: Bin Packing Problem (BPP) is a classical combinatorial optimization problem of graph theory, which has been proved to be NP-complete, and has high computational complexity. DNA self-assembly, a formal model of crystal growth, has been proposed as a mechanism for the bottom-up fabrication of autonomous DNA computing. In this paper, the authors propose a DNA self-assembly model for solving the BPP, this model consists of two units: grouping based on binary method and subtraction system. The great advantage of the model is that the number of DNA tile types used in the model is constant and it can solve any BPP within linear time. This work demonstrates the ability of DNA tiles to solve other NP-complete problems in the future.

Date: 2012
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 4018/jncr.2012010101 (application/pdf)

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:igg:jncr00:v:3:y:2012:i:1:p:1-15

Access Statistics for this article

International Journal of Natural Computing Research (IJNCR) is currently edited by Xuewen Xia

More articles in International Journal of Natural Computing Research (IJNCR) from IGI Global
Bibliographic data for series maintained by Journal Editor ().