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