МЕТИС - METIS
МЕТИС это программный пакет для разбиение графа который реализует различные многоуровневые алгоритмы.[1][2] Многоуровневый подход METIS состоит из трех этапов и включает несколько алгоритмов для каждого этапа:
- Увеличьте граф, создав последовательность графов G0, ГРАММ1, ..., ГРАММN, где G0 - исходный граф, и для каждого 0 ≤ i ≤ j ≤ N количество вершин в Gя больше, чем количество вершин в Gj.
- Вычислить разбиение GN
- Проецируйте раздел обратно через последовательность в порядке GN, ..., ГРАММ0, уточняя его по каждому графу.
Окончательное разбиение, вычисленное на третьем этапе (уточненное разбиение, спроецированное на G0) является разбиением исходного графа.
Рекомендации
- ^ Джордж Карипис и Випин Кумар (1995). METIS - Система разбиения неструктурированных графов и упорядочивания разреженных матриц, версия 2.0 (Технический отчет).[постоянная мертвая ссылка ]
- ^ Карипис Г. и Кумар В. (1999). «Быстрая и качественная многоуровневая схема разбиения нерегулярных графов». Журнал SIAM по научным вычислениям. 20 (1): 359. CiteSeerX 10.1.1.39.3415. Дои:10.1137 / S1064827595287997.
внешняя ссылка
 | Этот алгоритмы или же структуры данных -связанная статья является заглушка. Вы можете помочь Википедии расширяя это. |