Graph Partitioning Models for Parallel Computing

Abstract

Calculations can naturally be described as graphs in which vertices represent computation and edges reflect data dependencies. By partitioning the vertices of a graph, the calculation can be divided among processors of a parallel computer. However, the standard methodology for graph partitioning minimizes the wrong metric and lacks expressibility. We survey several recently proposed alternatives and discuss their relative merits.

Publication
Parallel Computing
Date
Citation
B. Hendrickson, T. G. Kolda. Graph Partitioning Models for Parallel Computing. Parallel Computing, Vol. 26, No. 12, pp. 1519-1534, 2000. https://doi.org/10.1016/S0167-8191(00)00048-X

Keywords

Graph partitioning; hypergraph partitioning; parallel computing

BibTeX

@article{HeKo00,  
author = {Bruce Hendrickson and Tamara G. Kolda}, 
title = {Graph Partitioning Models for Parallel Computing}, 
journal = {Parallel Computing}, 
volume = {26}, 
number = {12}, 
pages = {1519--1534}, 
month = {November}, 
year = {2000},
doi = {10.1016/S0167-8191(00)00048-X},
}