Universität Paderborn - Home Universität Paderborn
Die Universität der Informationsgesellschaft

Quick Links

External Links

Graph Partitioning

Given a graph, the problem is to assign its vertices to a given number of partitions, such that all partitions contain the same number of vertices and the number of cut edges, that is the edges incident to vertices of different partitions, is minimized. It is known, that this problem is NP-complete.
Since the problem occurs in many applications that express structural properties as graphs, heuristics have been developed that can generate solutions of sufficient quality very quickly. The most popular state of the art implementations are Metis and Jostle, which are based on a multilevel scheme and the vertex exchange heuristic of Kerninghan and Lin.

Picture
12 partitioning of the graph 'biplane9'.

The Party Graph Partitioning Library

Though its overall stucture is very similar to that of Metis and Jostle, the Party graph partitioning library differs from these libraries since it is based on analytical results. To generate the hierarchy of levels, we apply a 2-approximation algorithm for a maximum weighted matching, and the vertex exchange heuristic is inspired by a result showing a certain bisection bound for 4-regular graphs.

Shape Optimized Partitioning

In our experiments we have noticed that minimizing the number of cut edges does not necessarily lead to a desired solution. Furhter investigations have shown, that shape optimized partitionings usually have less boundary vertices and surprisingly also often cause less cut edges. We are currently developing a library containing different heuristics to compute such partitionings. Furthermore, applying this metric, connectivity of the partitions can be guaranted, and in case of a repartitioning problem, also the resulting vertex migration is low.
For a visual comparison, partitionings of a 100x100 grid computed by Metis, Jostle, Party and a shape optimized solution are shown below. Please note, that none of the heuristics is actually aware of the graph being a grid and that no coordinates are used.

Picture Picture Picture
kmetis
pmetis
vmetis
Picture Picture Picture
jostle
party
shape optimized

Index A – Z | Impressum | Webmaster | Modified: 20.5.2005