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.
Graph partitioning; hypergraph partitioning; parallel computing
@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},
}