Algorithm 1003
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Mar 20, 2020
- Source ID
- 10.1145/3337792
Entities
People
- Jennifer Scott
- S. Nuri Yeralan
- Timothy A. Davis
- William Ward Hager
Organizations
- National Science Foundation
- Office of Naval Research
- University of Florida