Abstract
Consider a tree T with n vertices, in which each vertex is associated with a nonnegative integer weight and each edge is associated with a positive integer cost. A partition of T is a set of subtrees induced by removing some edges. Let l <= u be two nonnegative integers. An [l, u]-partition is a partition such that the total weight of each subtree is in [l, u]. A p-[l, u]-partition is an [l, u]-partition with p subtrees. The cost of a partition is the total cost of the removed edges. The focus of this thesis is the following two problems: (1) the problem of finding a p-[l, u]-partition and (2) the problem of finding a minimum-cost [l, u]-partition. For (1), an O(n p^{4} loglog p / log^{2} p)-time algorithm is presented. For (2), its NP-hardness is proved. In addition, an O(n u^{2} loglog u / log^{2} u)-time pseudo-polynomial algorithm is presented. The presented algorithms for (1) and (2) improve, respectively, the previous upper bounds from O(n p^{4}) and O(n u^{2}). The improvement is achieved by an efficient application of the current best algorithm for computing the (min, +)-convolution of two vectors to reduce the running time of the previous algorithms. This thesis also considers the following nature extension of (1) and (2): finding a minimum-cost p-[l, u]-partition. For this extended problem, an O(n u^{2} p^{2} loglog p / log^{2} p)-time algorithm is presented.