An Algorithm for Partitioning a Tree Into Sibling Subtree Clusters Weighted in a Given Range

Assume that each vertex of an arbitrary n-vertex tree T is assigned a nonnegative integer weight. This paper considers partitioning the vertices of tree T into p disjoint clusters such that the total weight of each cluster is at least l and at most u, where l and u are given integers with l<;u. Such a partition can be called an [l, u]partition. Whereas traditional [l, u]partition algorithms for trees only allow that a cluster corresponds to a subtree, our algorithm also considers clusters containing several subtrees as long as these subtrees have the same parent node or their root vertices are adjacent siblings. We call this [l, u]sibling partitioning. We deal with two problems of [l, u]sibling partitioning for a given tree: the minimal partition problem is to find an [l, u]sibling partitioning with the minimum number of clusters; the p-partition problem is to find an [l, u]sibling partitioning with a given number p of clusters. In this paper, we present the first polynomial-time algorithm to solve the two problems.