An (O)over-tilde(2(n)) volume molecular algorithm for Hamiltonian path

Authors
Fu, B Beigel, R Zhou, FX
Citation
B. Fu et al., An (O)over-tilde(2(n)) volume molecular algorithm for Hamiltonian path, BIOSYSTEMS, 52(1-3), 1999, pp. 217-226
Citations number
23
Categorie Soggetti
Experimental Biology
Journal title
BIOSYSTEMS
ISSN journal
03032647 → ACNP
Volume
52
Issue
1-3
Year of publication
1999
Pages
217 - 226
Database
ISI
SICI code
0303-2647(199910)52:1-3<217:A(VMAF>2.0.ZU;2-L
Abstract
We design volume-efficient molecular algorithms for all problems in #P, usi ng only reasonable biological operations. In particular, we give a polynomi al-time O(2(n)n(2) log(2) n)-volume algorithm to compute the number of Hami ltonian paths in an n-node graph. This improves Adleman's celebrated n!-vol ume algorithm for finding a single Hamiltonian path. (C) 1999 Elsevier Scie nce Ireland Ltd. All rights reserved.