METIS とは

METISは、さまざまなマルチレベルアルゴリズムを実装するグラフ分割用のソフトウェアパッケージです。
METISのマルチレベルアプローチには3つのフェーズがあり、各フェーズにいくつかのアルゴリズムが付属しています。
 グラフG0、G1、…、GNのシーケンスを生成してグラフを粗くします。ここでG0は元のグラフであり、0≤i≤j≤Nのそれぞれについて、Giの頂点の数は頂点の数よりも大きいGj。 GNのパーティションを計算します。パーティションを、GN、…、G0の順番でシーケンスに戻して、各グラフに関して整理します。
第3フェーズ(G0に投影された洗練されたパーティション)の間に計算された最後のパーティションは、元のグラフのパーティションです。