Paper Info
Title
Quality matching and local improvement for multilevel graph-partitioning
Abstract
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 1 2 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 2 k 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.
Year
DOI
Venue
2000
10.1016/S0167-8191(00)00049-1
Parallel Computing
Keywords
Field
DocType
quality matching,local improvement,multilevel graph-partitioning,multilevel,bisection-width,matching,graph-partitioning,time complexity,graph partitioning,satisfiability,upper bound
Approximation algorithm,Discrete mathematics,Computer science,Upper and lower bounds,Bipartite graph,Matching (graph theory),Factor-critical graph,Time complexity,3-dimensional matching,Graph partition
Journal
Volume
Issue
ISSN
26
12
Parallel Computing
Citations 
PageRank 
References 
33
2.77
20
Authors
3
Name
Order
Citations
PageRank
Burkhard Monien12199279.35
Robert Preis233625.95
Ralph Diekmann3332.77