zbMATH — the first resource for mathematics

Graph partitioning models for parallel computing. (English) Zbl 0948.68130
Summary: 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.

68R10 Graph theory (including graph drawing) in computer science
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDF BibTeX Cite
Full Text: DOI