A Scalable Contraction Phase for Parallel Graph Partitioning

processing.
The simplest case of graph partitioning is as follows: Given a graph G
= (V, E) and an integer k, the vertex set is to be partitioned such
that each partition block has the same size and minimize the edges
adjacent to vertices in different blocks.

Beginning, from the mid-90s, the most successful practicable codes use
a multi-level approach. We present a scalable coarsening phase for a
distributed memory, parallel multi-level partitioner and an
experimental evaluation thereof. The main contribution is using
high-quality matching algorithm with target functions different from
the edge weight. Also, the algorithm for finding matchings of vertices
that are not local to one process is more advanced than other codes we
are aware of.