chapter  14
34 Pages

Scotch and PT-Scotch Graph Partitioning Software: An Overview

ByFranc¸ois Pellegrini

Graph partitioning is a ubiquitous technique which has applications in many fields of computer science and engineering, especially among the CSC community. It is mostly used to help solve domain-dependent optimization problems modeled in terms of weighted or unweighted graphs, where finding good solutions amounts to computing, possibly recursively according to a divide-and-conquer framework, small vertex or edge cuts that balance the weights of the graph parts.