TSP Path: NOT Tour
- From: yangshengwen@xxxxxxxxx
- Date: 16 Jan 2006 00:26:00 -0800
It's easy to understand that Traveling Salesman Tour Problem is NPC (By
reduction from Hamiltonian Cycle). But how to understand that a
Traveling Salesman Path Problem is also NPC? Here, Tour means that the
salesman must return to the staring city, Path means that the salesman
will not return to the staring city, but just visiting each city once
and only once.
Can anybody help, please?
Thanks:)
.
- Follow-Ups:
- Re: TSP Path: NOT Tour
- From: Nicholas King
- Re: TSP Path: NOT Tour
- Prev by Date: Re: Subset Sum Problem
- Next by Date: Re: TSP Path: NOT Tour
- Previous by thread: Subset Sum Problem
- Next by thread: Re: TSP Path: NOT Tour
- Index(es):