Quality matching and local improvement for multilevel graph-partitioning

Multilevel strategies have proven to be very powerful approaches in order t o partition graphs efficiently. Their efficiency is dominated by two parts; the coarsening and the local improvement strategies. Several methods have been developed to solve these problems, but their efficiency has only been proven on an experimental basis. In this paper, we present new and efficien t methods for both problems, while satisfying certain quality measurements. For the coarsening part we develop a new approximation algorithm for maxim um weighted matching in general edge-weighted graphs. It calculates a match ing with an edge weight of at least 1/2 of the edge weight of a maximum wei ghted matching. Its time complexity is O(\ E \), with \ E \ being the numbe r of edges in the graph. Furthermore, we use the Helpful-Set strategy for t he local improvement of partitions. For partitioning graphs with a regular degree of 2k into two parts, it guarantees an upper bound of ((k - 1)/2)\ V \ + 1 on the cut size of the partition, with \ V \ being the number of ver tices. These quality methods used for the two parts of the multilevel appro ach lead to an efficient graph-partitioning concept. (C) 2000 Published by Elsevier Science B.V. All rights reserved.