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.]
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.]
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).
That's too vague to answer. Are you talking about a C64 or some super computer? How big a DNA computer?
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) ?
Lot's, it would provide a mechanism to produce near-optimal scheduling stategies for a lot of commercial problems. ____________________________________________________________________ Before a larger group can see the virtue of an idea, a smaller group must first understand it. "Stranger Suns" George Zebrowski The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------
participants (3)
-
DUBEAU_Guy＠srh.dgac.fr -
Jim Choate -
Jordan Dimov