Abusing a hypergraph partitioner for unweighted graph partitioning
Publication date
2013
Authors
Fagginger Auer, B.O.
Bisseling, Rob H.
Editors
Bader, David A.
Meyerhenke, Henning
Sanders, Peter
Wagner, Dorothea
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
Abstract
We investigate using the Mondriaan matrix partitioner for unweighted graph partitioning in the communication volume and edgecut metrics. By converting the unweighted graphs to appropriate matrices, we measure Mondriaan’s performance as a graph partitioner for the 10th DIMACS challenge on graph partitioning and clustering. We find that Mondriaan can effectively be used as a graph partitioner: w.r.t. the edge-cut metric, Mondriaan’s average results are within 21% of the best known results as listed in Chris Walshaw’s partitioning archive.
Keywords
Taverne
Citation
Fagginger Auer, B O & Bisseling, R H 2013, Abusing a hypergraph partitioner for unweighted graph partitioning. in D A Bader, H Meyerhenke, P Sanders & D Wagner (eds), Graph Partitioning and Graph Clustering. vol. 588, Contemporary Mathematics, American Mathematical Society, Providence, Rhode Island, pp. 19-35. https://doi.org/10.1090/conm/588/11707