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

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

RESEARCH
PROJECTS
PUBLICATIONS
TEACHING
PEOPLE
SERVICE


Impressum
Webmaster

AG Logo-Small  
 
Graph-Partitioning

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

PARTY Partitioning Library

Introduction

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.

Contact

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
Mathematics
Warburgerstr. 100
33098 Paderborn
Germany

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 -