zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A polynomial-time DNA computing solution for the bin-packing problem. (English) Zbl 1191.68309

Summary: We suggest here an algorithm based on stickers for the DNA computing model [S. Roweis et al., “A sticker-based model for DNA computation”, Discrete Math. Theor. Comput. Sci. 44, 1–29 (1999; Zbl 0919.68027)] that solves the well-known Bin-Packing Problem (BPP), that belongs to the class of NP-hard problems in the strong sense, in 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 BPP in such a model.

MSC:
68Q05Models of computation (Turing machines, etc.)
68Q10Modes of computation
68W10Parallel algorithms
References:
[1]Adleman, L.: Molecular computation of solutions to combinatorial problems, Science 266, 1021-1024 (1994)
[2]M. Amos, DNA Computation, Ph.D. Thesis, Department of Computer Science, The University of Warwick, 1997.
[3]W.-L. Chang, M. Guo, Resolving the 3-dimensional matching problem and the set-packing problem in Adleman – Lipton’s model, in: IASTED International Conference, Networks, Parallel and Distributed Processing and Applications, Japan, 2002, pp. 455 – 460.
[4]Chang, W. L.; Guo, M.: Solving the set-cover problem and the problem of exact cover by 3-sets in the adleman – lipton’s model, Biosystems 72, 263-275 (2003)
[5]Chang, W. L.; Ho, M.; Guo, M.: Fast parallel molecular algorithms for DNA-based computation: factoring integers, IEEE transactions on nanobioscience 4, No. 2, 149-163 (2005)
[6]Chang, W. L.: Fast parallel DNA-based algorithms for molecular computation: the set-partition problem, IEEE transactions on nanobioscience 6, No. 1, 346-353 (2007)
[7]Chang, W. -L.; Ren, T. -T.; Luo, J.; Feng, M.; Guo, M.; Lin, K. W.: Quantum algorithms for bio-molecular solutions of the satisfiability problem on a quantum machine, IEEE transactions on nanobioscience 7, No. 3, 215-222 (2008)
[8]Chang, W. -L.; Ho, M.; Guo, M.: Molecular solution for the subset-sum problem on DNA-based supercomputing, Biosystems 73, 117-130 (2004)
[9]Darehmiraki, M.; Nehi, H. M.: Molecular solution to the 0 – 1 knapsack problem based on DNA computing, Applied mathematics and computation 187, 1033-1037 (2007) · Zbl 1114.65328 · doi:10.1016/j.amc.2006.09.020
[10]Darehmiraki, M.; Nehi, H. M.: A surface-based DNA algorithm for the solving binary knapsack problem, Applied mathematics and computation 188, 1991-1994 (2007) · Zbl 1113.92026 · doi:10.1016/j.amc.2006.11.073
[11]B. Fu, Volume bounded molecular computation, Ph.D. Thesis, Department of Computer Science, Yale University, 1997.
[12]Garey, R.; Johnson, D. S.: Computers and intractability: A guide to the theory of NP-completeness, (1979)
[13]Guo, M.; Ho, M.; Chang, W. -L.: Fast parallel molecular solution to the dominating-set problem on massively parallel bio-computing, Parallel computing 30, 1109-1125 (2004)
[14]Hennessy, J. L.; Patterson, D. A.; Goldberg, D.: Computer architecture: A quantitative approach, (2002) · Zbl 1003.68001
[15]Hsieh, S. -Y.; Chen, M. -Y.: A DNA-based solution to the graph isomorphism problem using adleman – lipton model with stickers, Applied mathematics and computation 197, 672-686 (2008) · Zbl 1171.68009 · doi:10.1016/j.amc.2007.08.005
[16]Hsieh, S. -Y.; Huang, C. -W.; Chou, H. -H.: A DNA-based graph encoding scheme with its applications to graph isomorphism problems, Applied mathematics and computation 203, 502-512 (2008) · Zbl 1228.68020 · doi:10.1016/j.amc.2008.04.041
[17]Lipton, R. J.: DNA solutions of hard computational problems, Science 268, 542-545 (1995)
[18]Pérez-Jiménez, M. J.; Sancho-Caparrini, F.: Solving knapsack problems in a sticker-based model, Lecture notes in computer science 2340, 161-171 (2002) · Zbl 1065.68555 · doi:http://link.springer.de/link/service/series/0558/bibs/2340/23400161.htm
[19]Quyang, Q.; Kaplan, P. D.; Liu, S.; Libchaber, A.: DNA solution of the maximal clique problem, Science 278, 446-449 (1997)
[20]Roweis, S.; Winfree, E.; Burgoyne, R.; Chelyapov, N.; Goodman, M.; Rothemund, P.; Adleman, L.: A sticker-based model for DNA computation, Journal of computational biology 5, 615-629 (1998)
[21]Watson, J.; Crick, F.: Molecular structure of nucleic acids; a structure for deoxyribose nucleic acid, Nature 171, No. 4356, 737-738 (1953)