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



How are these "minimal paths" called.
Posted:
Mar 9, 2004 5:19 PM


Let G=(V,E) be a connected graph without loops or parallel edges and W some subset of V. Consider all finite paths through W, (which should not necessairly be closed, may involve some nodes from V\W and which may go through the same node more than once.) Among all these paths, take those with a minimal length. How are they called? How is this minimal length called? Is anything done in this direction, does any bibliography exist?
This looks a bit like a real travelling salesman through the cities from the set W, where the salesman is also allowed to use the cities from V\W, and where each connection has weight 1. 
Best regards, Alex.
PS. My real emailaddress is formed by deleteing the letter combination "loeschedies" from the email address given.



