Karp, R. M.


The traveling salesman problem and minimum spanning trees

Classics

This paper explores new approaches to the symmetric traveling-salesman problem in which 1-trees, which are a slight variant of spanning trees, play an essential role. A 1-tree is a tree together with an additional vertex connected to the tree by two edges. We observe that (i) a tour is precisely a 1-tree in which each vertex has degree 2, (ii) a minimum 1-tree is easy to compute, and (iii) the transformation on “intercity distances” cij → Cij + πi + πj leaves the traveling-salesman problem invariant but changes the minimum 1-tree. Operations Research, 18, 1138–1162.