title: An O(2n) volume molecular algorithm for Hamiltonian path.
abstract: 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.
authors.affiliation: Epson Palo Alto Laboratory, Epson Research and Development, Inc., Palo Alto, CA 94304, USA. fu.bin@erd.epson.com
authors.forename: B
authors.initials: B
authors.lastname: Fu
authors.forename: R
authors.initials: R
authors.lastname: Beigel
authors.forename: F X
authors.initials: FX
authors.lastname: Zhou
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology; D004247:DNA / Q000032:analysis*; D006801:Humans; D008958:Models, Molecular
chemical_list: D004247:DNA