A Shifting Algorithm for Min-Max Tree Partitioning
Ronald I. Becker, Stephen R. Schach, Yehoshua Perl · Journal of the ACM · 1982
The problem of finding a mm-max partmon of a weJghted tree T with n veruces into q subtrees by means of k = q -1 cuts is considered.A top-down shifting algorithm for this problem ts presented An outhne is given of an efficJent implementatmn of the algorithm wtth complexity O(k3rd(T) + kn), where rd(T) ts the number of edges m the radius of T Categories and Subject Descriptors F 2 2 [Analysis of Algorithms and Problem Complexity].Nonnumencai Algorithms and Problems; G 2 2 [Discrete Mathematics]' Graph Theory--network problems, trees General Terms.