Next: 8.4.1 A Greedy Algorithm for TSP Up: 8. Undirected Graphs Previous: 8.3.3 Kruskal's Algorithm

8.4 Traveling Salesman Problem

REF.: Eugene L Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B.Shmoys, editors. The Traveling Salesman Problem. John Wiley & Sons, 1985.

Tour (Hamilton) (Hamiltonian cycle)
Given a graph with weights on the edges a tour is a simple cycle that includes all the vertices of the graph. For examples of tours, see Figure 6.30.
TSP
Given a graph with weights on the edges, find a tour having a minimum sum of edge weights.
NP-hard problem

**Figure 8.14:** A six-city TSP and some tours
$\begin{figure} \centerline{\psfig{figure=figures/Ftsp1.ps,width=6in}} \end{figure}$

eEL,CSA_Dept,IISc,Bangalore