Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
1971 | 10.1007/BF01584070 | Programs in Mathematics |
Keywords | Field | DocType |
Mathematical Method, Iterative Method, Span Tree, Search Tree, Minimum Span Tree | Discrete mathematics,Branch and bound,Mathematical optimization,Combinatorics,Minimum degree spanning tree,Distributed minimum spanning tree,Euclidean minimum spanning tree,Combinatorial optimization,Travelling salesman problem,Spanning tree,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
1 | 1 | 1436-4646 |
Citations | PageRank | References |
426 | 356.98 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Held | 1 | 911 | 509.89 |
| R. M. Karp | 2 | 14427 | 3783.81 |