Biomedical subjects
Publications and source records attributed to R Beigel.
The length of DNA strands is an important resource in DNA computing. We show how to decrease strand lengths in known molecular algorithms for some NP-complete problems, such as like 3-SAT and Independent Set, without substantially increasing their running time or volume.
We design volume-efficient molecular algorithms for all problems in #P, using only reasonable biological operations. In particular, we give a polynomial-time 0(2(n)n2log2n)-volume algorithm to compute the number of Hamiltonian paths in an n-node graph. This improves Adleman's celebrated n!-volume algorithm for finding a single Hamiltonian path.