METIS

METIS - это программный пакет для разбиения графа, который реализует различные многоуровневые алгоритмы. Многоуровневый подход METIS состоит из трех этапов и включает несколько алгоритмов для каждого этапа:

1. Увеличить размер графика путем создания последовательности графиков G 0, G 1,..., G N, где G 0 - исходный граф, и для каждого 0 ≤ i ≤ j ≤ N количество вершин в G i больше, чем количество вершин в G j.
2. Вычислить раздел G N
3. Спроецировать раздел обратно через последовательность в порядке G N,..., G 0, уточняя это по отношению к каждому графу.

Заключительное разбиение, вычисленное на третьем этапе (уточненное разбиение, спроецированное на G 0), является разбиением исходного графа.

• Веб-сайт METIS

.