A SHIFTING ALGORITHM FOR CONSTRAINED MIN-MAX PARTITION ON TREES

Let T = (V, E) be a rooted tree with n edges. We associate nonnegative weight w(v) and size s(v) with each vertex v in V. A q-partition of T into q connected components T1, T2,..., T(q) is obtained by deleting k = q-1 edges of T, 1 less-than-or-equal-to k < n. The weight W(T(i)) (or size S(T(i)) of component T(i) is then the sum of the weights (siz es) of the vertices of T(i). The height h(T) is the maximum number of edges of paths having one end at the root. If P is a partition with co mponents T1.....T(q) let W(p) = max(1 less-than-or-equal-to i less-tha n-or-equal-to q W(T(i)). The following two problems are considered: (1 ) Size-constrained min-max problem: Find a q-partition of T for which W(P) is a minimum over all partitions P satisfying S(T(i)) less-than-o r-equal-to M (M > 0). (2) Height-constrained min-max problem: Find a q -partition of T for which W(P) is a minimum over all partitions P sati sfying height h(T(i)) less-than-or-equal-to H (H is a positive integer ). The first problem is shown to be NP-complete, while a polynomial al gorithm is presented for the second problem.