Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Is this "travelling salesman problem"/"routing problem" version known?

4 views
Skip to first unread message

Alexander Malkis

unread,
Mar 12, 2004, 6:07:48 PM3/12/04
to
Hello everyone!

Cannot find anything about the following problem. Could anyone help?
Have any decision versions or algorithms been explored?

Let G=(V,E) be an undrected graph (without parallel edges or loops
(v,v)), let W be some subset of V.

(a) Find a shortest path (not necessairly closed) in G that goes through
each element of W at least once.
(b) Find the length of such path from (a).

--
Best regards,
Alex.

PS. To email me, remove "loeschedies" from the email address given.

0 new messages