×

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.

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