Abusing a hypergraph partitioner for unweighted graph partitioning

B.O. Fagginger Auer, R.H. Bisseling

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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.
Original languageEnglish
Title of host publicationGraph Partitioning and Graph Clustering
EditorsDavid A. Bader, Henning Meyerhenke, Peter Sanders, Dorothea Wagner
Place of PublicationProvidence, Rhode Island
PublisherAmerican Mathematical Society
Pages19-35
Volume588
DOIs
Publication statusPublished - 2013

Publication series

NameContemporary Mathematics

Fingerprint

Dive into the research topics of 'Abusing a hypergraph partitioner for unweighted graph partitioning'. Together they form a unique fingerprint.

Cite this