Algorithm 1003
Open Access
- 20 March 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 46 (1) , 1-18
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.Keywords
Funding Information
- National Science Foundation (0620286, 1522629, 1514406)
- Office of Naval Research (N00014-11-1-0068, N00014-15-1-2048, N00014-18-1-2100)
This publication has 14 references indexed in Scilit:
- An Efficient Hybrid Algorithm for the Separable Convex Quadratic Knapsack ProblemACM Transactions on Mathematical Software, 2016
- Think Locally, Act Globally: Highly Balanced Graph Partitioning2013
- The Zoltan and Isorropia Parallel Toolkits for Combinatorial Scientific Computing: Partitioning, Ordering and ColoringScientific Programming, 2012
- Benchmarking optimization software with performance profilesMathematical Programming, 2002
- Graph Partitioning and Continuous Quadratic ProgrammingSIAM Journal on Discrete Mathematics, 1999
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular GraphsSIAM Journal on Scientific Computing, 1998
- Scotch: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs1996
- Min-cut clusteringMathematical Programming, 1993
- Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph PartitioningOperations Research, 1989
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970