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 NPcomplete.
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.
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 2approximation algorithm
for a maximum weighted matching, and the vertex exchange heuristic is
inspired by a result showing a certain bisection bound for 4regular
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.
kmetis

pmetis

vmetis

jostle

party

shape optimized

Index A – Z  Impressum  Webmaster  Modified: 20.5.2005