Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
Is this "travelling salesman problem" version known?
Replies:
5
Last Post:
Mar 16, 2004 3:57 PM




Re: Is this "travelling salesman problem" version known?
Posted:
Mar 12, 2004 9:33 AM


anonymous@mathforum.org wrote: > If you are required to return to the starting point, > then this is the "Hamiltonian cycle" problem, > which is knownto be NPhard.
No. The path is allowed to be open (and in the problem I'm working on, it is always open except we have only one city)
I din't even see a proof of NPhardness for the "open path" version of TSP. Here help is appreciated too.
 Best regards, Alex.
PS. To email me, remove "loeschedies" from the email address given.



