Covering Nodes by K Node-Disjoint Trees with Additional Constraints

摘要

Given a complete undirected weighted graph G with k+n nodes including a subset K of k (1 less than or = k less than or = n) the problem of covering, at minimum cost, the nodes of G by k node-disjoint trees such that each tree includes no more than one node from K is considered. A 0(n sq = k sq n) time algorithm that may be regarded as a combination of a minimum spanning tree algorithm with a type of augmenting path procedure for matchings in bipartite graphs is used. The inclusion of additional equality constraints on the degrees of the nodes belonging to an arbitrary subset K' of K is considered. It is shown that the same algorithm also solves this restricted version of the problem in 0(n sq + (D+k-/K'/)sq n) time, where D is the sum of the required degrees for the nodes in set K'. As a special case, the algorithm turns out to be a 0(n sq + D sq n) time algorithm for the minimum spanning tree having degree equal to D on a specified node.