In "Molecular computations of solutions to combinatorial problems.", Adleman uses biocomputing to solve the directed Hamiltonian path problem for a seven vertex graph. The approach requires an exponential number of molecules, and Avogadro's number implies that such experiments are inconceivable for graphs larger than about n=70. [Skiena] On Thu, 30 Nov 2000, DUBEAU Guy wrote:
I am curious to know the maximum size of graphs than can be solved by existing computers (electronic or DNA-based).
Also, what would be the commercial fallout of finding an algorithm to solve the Hamiltonian path problem rapidly for big graphs (500 points and over) ?
Thanks in advance,
Guy Dubeau
[By the way, I can't check the Web since I have no Internet connection, just the e-mail.]