| Full text | |
| Author(s): |
Alonso Sanches, Carlos Alberto
;
Soma, Nei Yoshihiro
Total Authors: 2
|
| Document type: | Journal article |
| Source: | Applied Mathematics and Computation; v. 215, n. 6, p. 2055-2062, NOV 15 2009. |
| Web of Science Citations: | 17 |
| Abstract | |
It is suggested here an algorithm based on stickers for the DNA Computing model {[}S. Roweis, E. Winfree, R. Burgoyne, N. Chelyapov, M. Goodman, P. Rothemund, L. Adleman, A sticker-based model for DNA Computation, Journal of Computational Biology 5 (1998) 615-629] that solves the well known Bin-Packing Problem (BPP), that belongs to the class N P-Hard in the strong sense, in a time bounded by O(n(2)q), where n is the quantity of items and q the space requirements expressed in bits. To the best of the authors' knowledge, this is the first polynomial time algorithmic solution for the BPP in such a model. (C) 2009 Elsevier Inc. All rights reserved. (AU) | |
| FAPESP's process: | 06/05325-1 - Solving intractable problems through natural computing |
| Grantee: | Carlos Alberto Alonso Sanches |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |