In this paper we present a new algorithm for thek-partitioning problem which achieves an improved solution uality compared to known heuristics. We apply the principle of so called “helpful sets”, which has shown to be very efficient for graph bisection, to the directk-partitioning problem. The principle is extended in several ways. We introduce a new abstraction technique which shrinks the graph during runtime in a dynamic way leading to shorter computation times and improved solutions qualities. The use of stochastic methods provides further improvements in terms of solution quality. Additionally we present a parallel implementation of the new heuristic. The parallel algorithm delivers the same solution quality as the sequential one while providing reasonable parallel efficiency on MIMD-systems of moderate size.