The PARTY Partitioning Library, User Guide
Robert Preis and Ralf Diekmann
Department of Computer Science, University of Paderborn
Fuerstenallee 11, D-33102 Paderborn
e-mail: {robsy, diek}@uni-paderborn.de
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.
Full paper
in compressed postscript.
The PARTY-Library Home Page