PARTY - a Software Library for Graph Partitioning
Robert Preis, R. Diekmann · Civil-comp proceedings · 2009
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 me...