1 Answers
In mathematics, the multi-level technique is a technique used to solve the graph partitioning problem.
The idea of the multi-level technique is to reduce the magnitude of a graph by merging vertices together, compute a partition on this reduced graph, and finally project this partition on the original graph.
In the first phase the magnitude of the graph is reduced by merging vertices. The merging of vertices is done iteratively: of a graph a new coarser graph is created and of this new coarser graph an even more coarse graph is created. This is done until a certain small magnitude is reached. Thus graphs with different magnitudes are induced.
In the second phase a partition of the graph with the smallest magnitude – the coarsest graph – is computed.