Given a connected graph with edge costs, we seek a spanning tree having a specified degree at one vertex r, with cost as small as possible. A previous algorithm, using edge exchanges, has run time 0(V^2); we improve this to 0(E log log V+V log V). Here V and E are the number of vertices and edges. The algorithm uses edge exchanges ordered efficiently on a reduced graph; it also uses efficient algorithms for minimum spanning trees and priority queues.
Gabow, Harold N., "A Good Algorithm for Minimum Spanning Trees with a Degree Constraint ; CU-CS-105-77" (1977). Computer Science Technical Reports. 103.