Jump to navigation Jump to search
- Coarsen the graph by generating a sequence of graphs G0, G1, ..., GN, where G0 is the original graph and for each 0 ≤ i ≤ j ≤ N, the number of vertices in Gi is greater than the number of vertices in Gj.
- Compute a partition of GN
- Project the partition back through the sequence in the order of GN, ..., G0, refining it with respect to each graph.
The final partition computed during the third phase (the refined partition projected onto G0) is a partition of the original graph.
- George Karypis & Vipin Kumar (1995). METIS - Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 2.0 (Technical report).[permanent dead link]
- Karypis, G. & Kumar, V. (1999). "A fast and high quality multilevel scheme for partitioning irregular graphs". SIAM Journal on Scientific Computing. 20 (1): 359. CiteSeerX 10.1.1.39.3415. doi:10.1137/S1064827595287997.
|This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.|