The Held—Karp algorithm and degree-constrained minimum 1-trees
From MaRDI portal
Publication:4168404
DOI10.1007/BF01609023zbMath0387.90097MaRDI QIDQ4168404
No author found.
Publication date: 1978
Published in: Mathematical Programming (Search for Journal in Brave)
Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Applications of graph theory to circuits and networks (94C15)
Related Items (6)
A Lagrangean approach to the degree-constrained minimum spanning tree problem ⋮ Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length ⋮ Design of a degree-constrained minimal spanning tree with unreliable links and node outage costs. ⋮ A note on relatives to the Held and Karp 1-tree problem ⋮ Design of capacitated degree constrained min-sum arborescence ⋮ A multiperiod degree constrained minimal spanning tree problem
Cites Work
- Unnamed Item
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Matroid intersection algorithms
- Some Abstract Pivot Algorithms
- AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
- A PRIMAL APPROACH TO THE INDEPENDENT ASSIGNMENT PROBLEM
- The Traveling-Salesman Problem and Minimum Spanning Trees
- The traveling-salesman problem and minimum spanning trees: Part II
- Matroids and the greedy algorithm
This page was built for publication: The Held—Karp algorithm and degree-constrained minimum 1-trees
