Max-Min Tree Partitioning

Abstract

The max-rain k-partition algorithm may be formulated as follows: Given a tree T with n edges and a nonnegative weight associated with each vertex, assign a cut to each of k distinct edges of T so as to maximize the weight of the lightest resulting connected subtree. An algorithm for this problem is presented which initially assigns all k cuts to one edge incident with a terminal vertex of T; thereafter the cuts are shifted from edge to adjacent edge on the basis of local information. An efficient implementation with complexity O(k 2. rd(T) + kn), where rd(T) is the number of edges in the radius of T, is described. An algorithm for a simpler problem, namely, the partitioning of Tinto the maximum number of connected components whose weight is bounded below, is then described. Combined with the technique of binary search, it yields an alternative algorithm for the max-rain k-partition problem with complexity dependent on the range of the given weights.