Max-Min Tree Partitioning

Yehoshua Perl, Stephen R. Schach

Journal of the ACM · 1981 · 87 citations · 5 references

DOIFull text

Open access

Concepts

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.

References

5