ABSTRACT

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.