AESOP home


A Parallel Algorithm for Multilevel k-way Hypergraph Partitioning

Aleksandar Trifunovic, William J. Knottenbelt

Conference or Workshop Paper
ISPDC 2004, 3rd International Symposium on Parallel and Distributed Computing
June, 2004
IEEE Computer Society
DOI 10.1109/ISPDC.2004.6

In this paper we present a coarse-grained parallel multilevel algorithm for the k-way hypergraph partitioning problem. The algorithm significantly improves on our previous work in terms of run time and scalability behaviour by improving processor utilisation, reducing synchronisation overhead and avoiding disk contention. The new algorithm is also generally applicable and no longer requires a particular structure of the input hypergraph to achieve a good partition quality.

We present results which show that the algorithm has good scalability properties on very large hypergraphs with Theta(10^7) vertices and consistently outperforms the approximate partitions produced by a state-of-the-art parallel graph partitioning tool in terms of partition quality, by up to 27%.

PDF of full publication (115.5 kilobytes)
(need help viewing PDF files?)
Postscript of full publication (245 kilobytes)
(need help viewing Postscript files?)

Information from