METIS

This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: "METIS" – news · newspapers · books · scholar · JSTOR (August 2022) (Learn how and when to remove this message)

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:

1. 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.
2. Compute a partition of G_N
3. 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.

According to Metis authors Karypis and Kumar, "Metis is the Greek word for wisdom. Metis was a titaness in Greek mythology. She was the consort of Zeus and the mother of Athena. She presided over all wisdom and knowledge".^[3]

• METIS overview
• METIS on GitHub

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

• v
• t
• e