CDR: Re: Directed Hamiltonian path problem

[Jordan Dimov]

  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.]
>