COMBINING HELPFUL SETS AND PARALLEL SIMULATED ANNEALING FOR THE GRAPH-PARTITIONING PROBLEM∗

Publisher Website
Google Scholar
Abstract
In this paper we present a new algorithm for the k-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 direct k-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. All results are verified by experiments for various graphs and processor numbers.

This publication has 27 references indexed in Scilit: