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 …