Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are given integers such that 0≤l≤u. One wishes to partition G into connected components by deleting edges from G so that the total weight of each component is at least l and at most u. Such a partition is called an (l,u)‐partition. We deal with three problems to find an (l,u)‐partition of a given graph: the minimum partition problem is to find an (l,u)‐partition with the minimum number of components; the maximum partition problem is defined analogously; and the p‐partition problem is to find an (l,u)‐partition with a given number p of components. All these problems are NP‐hard even for series‐parallel graphs, but are solvable in linear time for paths. In this paper, we present the first polynomial‐time algorithm to solve the three problems for arbitrary trees.
