| Texto completo | |
| Autor(es): |
Alonso Sanches, Carlos Alberto
;
Soma, Nei Yoshihiro
Número total de Autores: 2
|
| Tipo de documento: | Artigo Científico |
| Fonte: | Applied Mathematics and Computation; v. 215, n. 6, p. 2055-2062, NOV 15 2009. |
| Citações Web of Science: | 17 |
| Resumo | |
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) | |
| Processo FAPESP: | 06/05325-1 - Resolução de problemas intratáveis através de computação natural |
| Beneficiário: | Carlos Alberto Alonso Sanches |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |