Richard M. Karp, Raymond E. Miller, et al.
STOC 1972
The relationship between the symmetric traveling-salesman problem and the minimum spanning tree problem yields a sharp lower bound on the cost of an optimum tour. An efficient iterative method for approximating this bound closely from below is presented. A branch-and-bound procedure based upon these considerations has easily produced proven optimum solutions to all traveling-salesman problems presented to it, ranging in size up to sixty-four cities. The bounds used are so sharp that the search trees are minuscule compared to those normally encountered in combinatorial problems of this type. © 1971 North-Holland Publishing Company.
Richard M. Karp, Raymond E. Miller, et al.
STOC 1972
Richard M. Karp
Journal of the ACM
Michael Held, Richard M. Karp
ACM National Meeting 1961
Richard M. Karp, Raymond E. Miller, et al.
Journal of the ACM