An Efficient Implementation of an Algorithm for Min-Max Tree Partitioning
Ronald I. Becker, Yehoshua Perl, Stephen R. Schach · Unisa Institutional Repository (University of South Africa) · 1982
An implementation of an algorithm for finding a min-max partition of a weighted tree T with n vertices into q subtrees by means of k = q-1 cuts is presented. The implementation is shown to have asymptotic complexity O(k3rd(T) + kn), where rd(T) is the number of edges in the radius of T.