Algorithm 1003: Mongoose, a Graph Coarsening and Partitioning Library Academic Article

abstract

• Partitioning graphs is a common and useful operation in many areas, from parallel computing to VLSI design to sparse matrix algorithms. In this article, we introduce Mongoose, a multilevel hybrid graph partitioning algorithm and library. Building on previous work in multilevel partitioning frameworks and combinatoric approaches, we introduce novel stall-reducing and stall-free coarsening strategies, as well as an efficient hybrid algorithm leveraging (1) traditional combinatoric methods and (2) continuous quadratic programming formulations. We demonstrate how this new hybrid algorithm outperforms either strategy in isolation, and we also compare Mongoose to METIS and demonstrate its effectiveness on large and social networking (power law) graphs.

authors

• Davis, Timothy

published proceedings

• ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE

author list (cited authors)

• Davis, T. A., Hager, W. W., Kolodziej, S. P., & Yeralan, S. N.

citation count

• 5

complete list of authors

• Davis, Timothy A||Hager, William W||Kolodziej, Scott P||Yeralan, S Nuri

publication date

• January 2020

publisher

• Association for Computing Machinery (ACM)  Publisher

published in

• ACM Transactions on Mathematical Software  Journal

keywords

• Graph Coarsening
• Graph Partitioning
• Vertex Matching

Digital Object Identifier (DOI)

• 10.1145/3337792

start page

• 1

end page

• 18

volume

• 46

issue

• 1

URL

• http://dx.doi.org/10.1145/3337792