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

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.

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