Third International Symposium on Parallel and Distributed Computing/Third International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks (ISPDC/HeteroPar'04) A Parallel Algorithm for Multilevel k-Way Hypergraph Partitioning Cork, Ireland July 05-July 07 ISBN: 0-7695-2210-6
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPDC.2004.6
In this paper we present a coarse-grained parallel multi-level 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 ?(107) 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%.
Citation:
Aleksandar Trifunovic, William J. Knottenbelt, "A Parallel Algorithm for Multilevel k-Way Hypergraph Partitioning," ispdc, pp.114-121, Third International Symposium on Parallel and Distributed Computing/Third International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks (ISPDC/HeteroPar'04), 2004 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb