ПОМЕЩАТЬ
 |
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 ), является разбиением исходного графа.
По словам авторов Метиды Кариписа и Кумара, «Метис - это греческое слово, обозначающее мудрость. Метида была титаницей в греческой мифологии. Она была супругой Зевса и матерью Афины. Она управляла всей мудростью и знаниями». [3]
Ссылки
[ редактировать ]- ^ Джордж Карипис и Випин Кумар (1995). METIS - Система разбиения неструктурированных графов и системы упорядочения разреженных матриц, версия 2.0 (Технический отчет). [ постоянная мертвая ссылка ]
- ^ Карипис Г. и Кумар В. (1999). «Быстрая и качественная многоуровневая схема разбиения нерегулярных графов». SIAM Журнал по научным вычислениям . 20 (1): 359. CiteSeerX 10.1.1.39.3415 . дои : 10.1137/S1064827595287997 . S2CID 3628209 .
- ^ Карипис, Георгий; Кумар, Випин (1997). METIS: пакет программного обеспечения для разделения неструктурированных графов, разделения сеток и вычисления упорядочивания разреженных матриц с уменьшением заполнения (отчет).
Внешние ссылки
[ редактировать ] | Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее . |