METIS

METIS is a software package for graph partitioning that implements various multilevel algorithms.^[1]^[2] METIS' multilevel approach has three phases and comes with several algorithms for each phase:

Coarsen the graph by generating a sequence of graphs G₀, G₁, ..., G_N, where G₀ is the original graph and for each 0 ≤ i ≤ j ≤ N, the number of vertices in G_i is greater than the number of vertices in G_j.
Compute a partition of G_N
Project the partition back through the sequence in the order of G_N, ..., G₀, refining it with respect to each graph.

The final partition computed during the third phase (the refined partition projected onto G₀) is a partition of the original graph.

References

^ 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.

External links

METIS website

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

[1] George Karypis & Vipin Kumar (1995). METIS - Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 2.0 (Technical report).^{[permanent dead link]}

[2] 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.

[1]

[2]