Parallel algorithms and applications · 1996 · 24 citations · 29 references
ComputingComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingData PartitioningGraph AlgorithmsParallel Algorithm DesignParallel ComputationParallel Computing SystemsAbstractionGraph PartitioningParallel EfficiencyParallel Graph AlgorithmsParallel PartitioningParallel Search AlgorithmsPartitioningSolution Quality Assessment
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.
29
Optimization by Simulated Annealing
Scott Kirkpatrick, C. D. Gelatt, M.P. Vecchi · Science · 1983 · 44.6K citations
Algebraic connectivity of graphs
Miroslav Fiedler · Czechoslovak Mathematical Journal · 1973 · 4K citations · Full text