Given an edge-weighted graph G = (V, E), a subset S subset of V, an integer k >= 1 and a real b >= 0, the minimum subpartition problem asks to find a family of k nonempty disjoint subsets X(1), X(2), ..., X(k) subset of S with d(X(i)) <= b, l <= i <= k, so as to minimize Sigma(1 <= i <= k) d(X(i)), where d(X) denotes the total weight of edges between X and V - X. In this paper, we show that the minimum subpartition problem can be solved in O(mn + n(2) log n) time. The result is then applied to the minimum k-way cut problem and the graph strength problem to improve the previous best time bounds of 2-approximation algorithms for these problems to O(mn + n(2) log n). (c) 2006 Elsevier B.V. All rights reserved.