Skip to main content

Research Repository

Advanced Search

A multi-level hypergraph partitioning algorithm using rough set clustering

Lotfifar, Foad; Johnson, Matthew

A multi-level hypergraph partitioning algorithm using rough set clustering Thumbnail


Authors

Foad Lotfifar



Contributors

Jesper Träff
Editor

Sascha Hunold
Editor

Francesco Versaci
Editor

Abstract

The hypergraph partitioning problem has many applications in scientific computing and provides a more accurate inter-processor communication model for distributed systems than the equivalent graph problem. In this paper, we propose a sequential multi-level hypergraph partitioning algorithm. The algorithm makes novel use of the technique of rough set clustering in categorising the vertices of the hypergraph. The algorithm treats hyperedges as features of the hypergraph and tries to discard unimportant hyperedges to make better clustering decisions. It also focuses on the trade-off to be made between local vertex matching decisions (which have low cost in terms of the space required and time taken) and global decisions (which can be of better quality but have greater costs). The algorithm is evaluated and compared to state-of-the-art algorithms on a range of benchmarks. The results show that it generates better partition quality.

Citation

Lotfifar, F., & Johnson, M. (2015). A multi-level hypergraph partitioning algorithm using rough set clustering. In J. Träff, S. Hunold, & F. Versaci (Eds.), Euro-Par 2015 : parallel processing : 21st International Conference on Parallel and Distributed Computing, Vienna, Austria, August 24-28, 2015, Proceedings (159-170). Springer Verlag. https://doi.org/10.1007/978-3-662-48096-0_13

Acceptance Date Jul 25, 2015
Online Publication Date Jul 25, 2015
Publication Date Jul 25, 2015
Deposit Date Oct 31, 2015
Publicly Available Date Jul 25, 2016
Publisher Springer Verlag
Pages 159-170
Series Title Lecture notes in computer science
Book Title Euro-Par 2015 : parallel processing : 21st International Conference on Parallel and Distributed Computing, Vienna, Austria, August 24-28, 2015, Proceedings.
ISBN 9783662480953
DOI https://doi.org/10.1007/978-3-662-48096-0_13

Files





You might also like



Downloadable Citations