www.upb.de Home [de]
Zurück zur Uni-Homepage

Zurück zur Homepage - Informatik Zurück zur Homepage - AG-Monien




>Graph Partitioning >Theory >Heuristics >Applications >PARTY >PadFEM >Graph Collection

PARTY Partitioning Library


The problem of partitioning a graph into a number of pieces is one of the fundamental tasks in computer science and has a number of applications e.g. in parallel programming or VLSI design. Finding optimal partitions according to different measures is in most cases NP-complete. Nevertheless, a large number of efficient partitioning heuristics have been developed during recent years. The performance of these methods in terms of computation time as well as quality of approximation is heavily influenced by choices of parameters and certain implementation details. Fortunately, the partitioning problem itself is clearly defined and its description leads to a small interface. Thus, efficient implementations of approximation heuristics can be re-used for different applications.
The PARTY partitioning library serves a variety of different partitioning methods in a very simple and easy way. Instead of implementing the methods directly, the user may take advantage of the ready implemented methods of the library. All implementations include latest developments to increase the performance of the partitioning heuristics. Two kinds of interfaces allow the use as stand-alone tool as well as the inclusion into application codes. The data-structures used as interface to PARTY are simple and easy to generate. Several research projects currently use the PARTY partitioning library to solve the partitioning problem.


If you wish to get more information about the PARTY Partitioning Library, please take a look at the User Guide of the current version or contact me via e-mail at Robert.Preis@upb.de.
You can obtain a copy of the code if you sign this license and send it to

Robert Preis
University of Paderborn
Warburgerstr. 100
33098 Paderborn

The code will be send to you electronically. Currently, Version 1.1 is distributed.

Version 1.1, 16.9.1996

  • R. Preis, R. Diekmann:
    The PARTY Partitioning-Library, User Guide - Version 1.1
    Technical Report tr-rsfb-96-024, University of Paderborn, Sep. 1996.
    see abstract or postscript

Test-Version 1.99

A new Test-Version 1.99 is out, together with a new user-manual.

Other Graph Partitioning Web Sites

  Robert Preis -