Engineering a scalable high quality graph partitioner
- 1 January 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We describe an approach to parallel graph partitioning that scales to hundreds of processors and produces a high solution quality. For example, for many instances from Walshaw's benchmark collection we improve the best known partitioning. We use the well known framework of multi-level graph partitioning. All components are implemented by scalable parallel algorithms. Quality improvements compared to previous systems are due to better prioritization of edges to be contracted, better approximation algorithms for identifying matchings, better local search heuristics, and perhaps most notably, a parallelization of the FM local search algorithm that works more locally than previous approaches.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- JOSTLE - Multilevel Graph Partitioning Software: An OverviewPublished by Civil-Comp, Ltd. ,2009
- Engineering Route Planning AlgorithmsLecture Notes in Computer Science, 2009
- A Parallel Approximation Algorithm for the Weighted Maximum Matching ProblemPublished by Springer Nature ,2008
- A new diffusion-based multilevel algorithm for computing graph partitions of very high qualityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Better Approximation of Betweenness CentralityPublished by Society for Industrial & Applied Mathematics (SIAM) ,2008
- Engineering Algorithms for Approximate Weighted MatchingPublished by Springer Nature ,2007
- Improved Linear Time Approximation Algorithms for Weighted MatchingsLecture Notes in Computer Science, 2003
- A simple approximation algorithm for the weighted matching problemInformation Processing Letters, 2002
- Mesh Partitioning: A Multilevel Balancing and Refinement AlgorithmSIAM Journal on Scientific Computing, 2000
- A Linear-Time Heuristic for Improving Network PartitionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982