Abstract
In this note we propose to find a degree-constrained minimum 1-tree in the Held—Karp algorithm [5, 6] for the symmetric traveling-salesman problem, and show that it is reduced to finding a minimum common basis of two matroids.
This is a preview of subscription content, log in via an institution to check access.
References
J. Edmonds, “Matroids and the greedy algorithm”,Mathematical Programming 1 (1971) 127–136.
S. Fujishige, “A primal approach to the independent assignment problem”,Journal of the Operations Research Society of Japan 20 (1977) 1–15.
F. Glover and D. Klingman, “Finding minimum spanning trees with a fixed number of links at a node”, in:Combinatorial programming methods and applications (D. Reidel, Dordrecht, 1975) pp. 191–201.
C. Greene and T.L. Magnanti, “Some abstract pivot algorithms”,SIAM Journal on Applied Mathematics 29 (1975) 530–539.
M. Held and R.M. Karp, “The traveling-salesman problem and minimum spanning trees”,Operations Research 18 (1970) 1138–1162.
M. Held and R.M. Karp, “The traveling-salesman problem and minimum spanning trees: part II”,Mathematical Programming 1 (1971) 6–25.
M. Iri and N. Tomizawa, “An algorithm for finding an optimal ‘independent’ assignment”,Journal of the Operations Research Society of Japan 19 (1976) 32–57.
J.B. Kruskal, “On the shortest spanning subtree of a graph and the traveling-salesman problem”,Proceedings of the American Mathematical Society 2 (1956) 48–50.
E.L. Lawler, “Matroid intersection algorithm”,Mathematical Programming 9 (1975) 31–56.
D.J.A. Welsh,Matroid theory (Academic Press, London, 1976).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Yamamoto, Y. The Held—Karp algorithm and degree-constrained minimum 1-trees. Mathematical Programming 15, 228–231 (1978). https://doi.org/10.1007/BF01609023
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01609023