(Degree-Constrained Minimum Weight Spanning Trees) Consider the minimum weight spanning tree problem, subject to the additional constraint that the number of tree arcs that are incident to a single given node s should be no greater than a given integer k. Consider adding a nonnegative weight w to the weight of all incident arcs of node s, solving the corresponding unconstrained spanning tree problem, and gradually increasing w until the degree constraint is satisfied.
(a) State a polynomial algorithm for doing this and derive its running time.
(b) Use this algorithm to solve the problem of Fig. 10.19, where the degree of node 1 is required to be no more than 2.
