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 computational mechanics 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 standalone 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.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £66 +P&P)