Quality matching and local improvement for multilevel graph-partitioning ?
Multilevel strategies have proven to be very powerful approaches in order to 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 efficient methods for both problems, while satisfying certain quality measurements. For the coarsening part we develop a new approximation algorithm for maximum weighted matching in general edge-weighted graphs. It calculates a matching with an edge weight of at least of the edge weight of a maximum weighted matching. Its time complexity is O(|E|), with |E| being the number of edges in the graph. Furthermore, we use the Helpful-Set strategy for the 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 vertices. These quality methods used for the two parts of the multilevel approach lead to an efficient graph-partitioning concept.
matching local improvement multilevel graph-partitioning bisection-width