реферат

Традиционная задача о разбиении графов сфокусирована на вычислении k-фазного сегмента графа такого, что деление ребер минимизировано, а каждый сегмент содержит одинаковое количество вершин (или, в случае взвешенного графа, каждый сегмент имеет одинаковую сумму весов вершин). Задача минимизации деления ребер может рассматриваться как цель, а требование того, чтобы сегменты были одинакового размера, может рассматриваться как ограничение. Эта одноцелевая задача разбиения графа с одним ограничением широко используется для статического распределения сети в научном параллельном моделировании.

Однако, этой одноцелевой задачи разбиения графа с одним ограничением не достаточно для вычислительных требований многих научных имитационных моделей. Например, в многофазовых сеточных вычислениях не достаточно одного ограничения для эффективной балансировки комплексных вычислений. Многофазовые вычисления состоят из m отдельных вычислительных фаз, каждая из которых отделяется определенным шагом синхронизации. В основном, количество вычислительной нагрузки для каждого элемента сетки различно на разных фазах. Таким образом, для эффективного параллельного выполнения этих многофазовых вычислений, необходимо так разделить сетку, чтобы вычисления на каждой фазе были сбалансированы, а количество взаимодействий между различными процессорами на каждой фазе было минимизировано.

Ключевая характеристика этой задачи состоит в том, что она требует алгоритма разбиения, учитывающего любое количество ограничений, а также и любое количество целей (минимизации или максимизации). [1]

Для представления многих ограничений балансировки, необходимо расширить традиционную модель графа. Каждая вершина, вместо одного веса, ассоциированного с ней, имеет вектор весов. Размер этого вектора - m. Этот размер соответствует количеству ограничений балансировки. Используя эту дополненную модель графа, можно сформулировать задачу разбиения графа со многими ограничениями. Рассчитать k-фазное разбиение так, чтобы каждый из m весов был индивидуально сбалансирован с установленным допуском. [1]

Иными словами, если c - вектор размера m, который определяет допуск разбалансировки нагрузки, тогда цель в этом определении задачи со многими ограничениями состоит в вычислении таких сегментов таких, что разбалансировка нагрузки относительно i-ого веса должна быть меньше чем c_i. Например, если мы имеем два веса (m=2), тогда вектор допуска c = {1.05, 1.5} показывает, что мы ищем разбиение такое, в котором разбалансировка нагрузки относительно первого веса должна быть меньше или равна 5%, а для второго веса - меньше или равна 50%. [1]

Пакет METIS. METIS - это программный пакет, предназначенный для разбиения больших нерегулярных графов и вычисления упорядочений разреженных матриц. Алгоритмы в METIS основаны на многоуровневом разбиении графов. Алгоритмы многоуровневого разбиения уменьшают размер графа путем стягивания вершин и ребер, разбивают меньший граф, а затем уточняют его для построения сегментов исходного графа. METIS использует новые решения, как для последовательного уменьшения графа, так и для улучшения разбиения в течение фазы уточнения. В процессе огрубления METIS использует алгоритмы, которые упрощают поиск высококачественного разбиения в огрубленном (coarser graph). Во время фазы детализации METIS в основном фокусируется на той части графа, которая расположена ближе всего к границам. Эти сильно оптимизированные алгоритмы позволяют METIS'у быстро находить высококачественные разбиения для широкого множества графов. [2]

Пакет METIS состоит из нескольких программ. Для разбиения графов в METIS имеется две программы: pmetis и kmetis. Они предназначены для разбиения неструктурированных графов на k равных частей. Для разбиения графов программа pmetis использует алгоритм многоуровневой рекурсивной бисекции (см. [3]). Программа kmetis использует алгоритм многоуровневого k-фазного разбиения (см. [4]). Обе эти программы способны производить высококачественное разбиение. Однако, в зависимости от входных данных, одна программа может быть эффективнее другой. Так, в основном kmetis является более эффективным для разбиения графа на более чем 8 частей. Для этих задач kmetis существенно быстрее, чем pmetis. В свою очередь, pmetis эффективнее для разбиения графа на малое количество частей. [2]

Основная структура многоуровневого k-фазного разбиения очень простая. Граф G = (V, E) сначала стягивается к малому количеству вершин, затем рассчитывается разбиение этого намного меньшего графа, а после этого полученное разбиение проектируется назад в оригинальный граф, путем последовательных улучшений на каждом уровне. Работа алгоритма представлена на рисунке 2.1.

Рисунок 2.1 - Многоуровневое k-фазное разбиение.

Фаза стягивания. На фазе стягивания (или фаза огрубления), из оригинального графа G₀ = (V₀, E₀) строится последовательность меньших графов G_i = (V_i, E_i) таких, что |V_i+1| < |V_i|. В большинстве схем стягивания, множество вершин графа G_i объединяются в одну вершину стянутого графа следующего уровня G_i+1. Пусть V_i^v - множество вершин графа G_i, объединенных для формирования вершины v графа G_i+1. Для того, чтобы разбиение стянутого графа было хорошим касательно оригинального графа, вес вершины v устанавливается равным сумме весов вершин из множества V_i^v. Также, для сохранения информации о связях в стянутом графе, ребра вершины v являются объединением ребер вершин из множества V_i^v. В случае, когда более чем одна вершина из множества V_i^v имеет ребро, связанное с одной и той же вершиной u, вес ребра {u, v} равен сумме весов этих ребер. Этот метод стягивания (огрубления) обладает следующими свойствами [4, 5]:
  - границы разбиений в стянутом графе эквивалентны границам тех же разбиений в уточненном графе;
  - сбалансированность разбиений стянутых графов приводит к сбалансированности разбиений уточненных графов.

Фаза начального разбиения. Вторая фаза алгоритма многоуровневого k-фазного разбиения - это вычисление k-фазного разбиения P_m стянутого графа G_m = (V_m, E_m) такого, что каждый сегмент содержит приблизительно |V₀| / k веса вершин оригинального графа. В течение стягивания веса вершин и ребер огрубленного графа были выбраны так, чтобы отражать веса вершин и ребер оригинального графа. Таким образом, G_m содержит адекватную информацию для удовлетворения требований сбалансированности разбиения и минимальных требований к границам разбиений. [4]

Один из вариантов получения начального k-фазного разбиения - это продолжение стягивания графа до тех пор, пока в нем не останутся k вершин. Эти стянутые k вершин могут служить начальным k-фазным разбиением оригинального графа. Есть две проблемы с таким решением. Во-первых, для большинства графов уменьшение размера графа на каждом шаге огрубления становится очень маленьким после нескольких шагов, что делает дорогостоящим каждый последующий шаг. Во-вторых, даже если имеется возможность стянуть граф всего до k вершин, веса этих вершин скорее всего будут весьма различны, что сделает начальное разбиение сильно разбалансированным. [4]

В пакете METIS, начальное разбиение вычисляется при помощи многоуровневого бисекционного алгоритма. Эксперименты авторов пакета показали, что этот алгоритм дает неплохое начальное разбиение, со сравнительно малыми затратами времени. [4]

Фаза уточнения. В течение фазы уточнения разбиение P_m стянутого графа G_m проектируется обратно в оригинальный граф, проходя через графы G_m-1, G_m-2, G_m-3, ... G₁. Так как каждая вершина v из G_i+1 содержит определенное подмножество вершин V_i^v из G_i, то P_i получаем из P_i+1 простым присваиванием множества вершин V_i^v сегменту P_i+1[v], т.е. P_i[u] := P_i+1[v], для всех u Є V_i^v. [4]

Следует отметить, что даже если разбиение G_i находится в локальном минимуме, проецируемое разбиение G_i-1 может не быть в локальном минимуме. Поскольку G_i-1 более детализирован, он имеет больше степеней свободы, которые могут быть использованы для дополнительного улучшения разбиение, а следовательно и для уменьшения количества разделяемых ребер.

Класс алгоритмов локального уточнения, которые имеют тенденцию к получению хороших результатов - это алгоритмы, основанные на алгоритме Кернигана-Лина и его модификациях [6, 7, 8]. Алгоритм Кернигана-Лина пошагово обменивает вершины между сегментами бисекции для уменьшения количества разделяемых ребер между сегментами до тех пор, пока разбиение не достигнет локального минимума.

В пакете METIS используются простые k-фазного алгоритмы уточнения, разработанные авторами пакета. Эти алгоритмы являются упрощенными версиями k-фазного алгоритма уточнения Кернигана-Лина. Сложность разработанных алгоритмов не зависит от количества сегментов, которые необходимо уточнить.

Пакет hMETIS. Пакет hMETIS предназначен для разбиения гиперграфов (см. [9]). hMETIS - это многоуровневый алгоритм бисекции гиперграфа. Формально, гиперграф G = (V, E) определяется как множество вершин V и множество гиперребер E, где каждое гиперребро есть подмножество множества ребер V, а размер гиперребра - это мощность этого подмножества (см. [10]).

Задачу, которую решает алгоритм hMETIS, можно определить следующим образом. Имеется гиперграф G = (V, E), где V - множество вершин и E - множество гиперребер. Имеется допуск (в документе khmetis.pdf; пояснением этого коэффициента есть формула, представленная ниже) общей разбалансировки нагрузки c, такой, что c >= 1.0. Цель - найти разбиение множества V на k непересекающихся подмножеств. V₁, V₂, ..., V_k - такие, что количество вершин в каждом множестве V_i ограничено неравенством :

Целевая функция, определенная для всего гиперграфа, должна быть оптимизирована.

hMETIS, также как и алгоритм многоуровневого k-фазного разбиения в пакете METIS, имеет три фазы: стягивание, начальное разбиение и уточнение. На фазе стягивания используются две схемы :
  - стягивание ребер (edge-coarsening);
  - стягивание гиперребер (hyperedge-coarsening).

Первая схема выбирает группы путем поиска пар вершин, которые принадлежат многим гиперребрам. В этой схеме каждая группа состоит, по крайней мере, из двух вершин, а каждая вершина принадлежит, по крайней мере, одной группе. Вторая схема находит максимально независимое множество гиперребер, а множества вершин, которые принадлежат каждому гиперребру, становятся группой вершин, которые должны быть стянуты. Пример выполнения стягивания гиперграфа показан на рисунке 2.2.

Рисунок 2.2 - Пример выполнения стягивания гиперграфа.

Фаза поиска начального разбиения в hMETIS эквивалентна фазе разбиения в многоуровневом k-путевом алгоритме разбиения графов. На фазе уточнения сегменты стянутого гиперграфа проецируются на следующий уровень уточненного гиперграфа, а для оптимизации целевой функции без нарушения ограничения балансировки разбиения используется алгоритм уточнения.

В случае бисекционного уточнения, алгоритм FM показывает довольно хорошие результаты (см. [11]). Для каждой вершины v алгоритм FM вычисляет "выгоду" (gain), которая является снижением в значении целевой функции, достигаемым перемещением вершины v в другой сегмент. Эти вершины помещаются в две очереди с приоритетами, каждая из которых соответствует одному сегменту в соответствии с вычисленной выгодой. Вначале все вершины разблокированы, т.е. их можно перемещать из одного сегмента в другой. Алгоритм пошагово выбирает разблокированную вершину с наибольшей "выгодой" из одной из двух приоритетных очередей, и перемещает ее в другой сегмент. После перемещения вершина v становится заблокированной, а "выгоды" вершин, смежных с v, обновляются. После каждого перемещения вершины алгоритм записывает значение целевой функции, полученного на текущем шаге. Один проход алгоритма заканчивается, когда больше нет разблокированных вершин. После этого проверяются записанные значения целевой функции, и выбирается тот шаг, когда целевая функция имела минимальное значение. Все вершины, перемещенные в другие сегменты, после этого шага возвращаются назад в свои начальные сегменты. После этого, полученное разбиение становится начальным для следующего прохода алгоритма.

Однако уточнение k-фазного разбиения значительно сложнее, потому что вершины могут перемещаться из одного сегмента во множество других, что комбинаторно увеличивает пространство оптимизации. Расширение для алгоритма FM для случая k-фазного уточнения описано в [12]. Этот алгоритм использует k(k-1) приоритетных очередей по одной для каждого типа перемещения. На каждом шаге алгоритма в каждой из k(k-1) находятся перемещения с наибольшей "выгодой". Выполняется перемещение с наибольшей "выгодой", которое сохраняет или улучшает условие баланса. После выполнения перемещения каждая из k(k-1) очередей обновляется. Сложность k-путевого уточнения значительно выше, чем для двух путевого уточнения.

Авторы пакета hMETIS разработали свой алгоритм уточнения - "жадный" алгоритм разбиения. Он выполняет множество итераций. На каждой итерации проверяются все вершины для определения, могут ли они быть перемещены так, чтобы целевая функция оптимизировалась при сохранении условия баланса.

Алгоритм работает следующим образом. Представим гиперграф G_i = (V_i, E_i) и его вектор разбиения P_i. Вершины просматриваются в случайном порядке. Пусть v такая вершина, где P_i[v] = a - сегмент, которому принадлежит вершина v. Если v является внутренним узлом сегмента a, то вершина не перемещается. Если v находится на границе сегмента, тогда v потенциально может быть перемещена в один из сегментов N(v), в котором есть вершины, смежные с v. Пусть N'(v) - подмножество N(v), которое содержит все сегменты b, такие, что перемещение вершины v в сегмент b не нарушает условие баланса. Тогда выбирается сегмент b Є N'(v), который приводит к наибольшему положительному уменьшению (выгоде) в целевой функции, а вершина v перемещается в него.

Пакет ParMETIS. PARMETIS - это параллельная библиотека, основанная на MPI - Message Passing Interface - протокол обмена сообщениями между процессами, выполняемыми параллельно, которая реализует набор алгоритмов для разбиения и переразбиения неструктурированных графов и вычисления упорядочений разреженных матриц. PARMETIS частично пригоден для параллельных численных моделей, содержащих большие неструктурированные сетки.

Алгоритмы в PARMETIS основаны на многоуровневом разбиении, которые были реализованы в пакете METIS. Однако PARMETIS расширяет функциональность, предоставляемую пакетом METIS и включает подпрограммы, которые преимущественно предназначены для параллельных вычислений широко-масштабных численных моделей. [13]

Параллельный алгоритм разбиения графов. Параллельный алгоритм также состоит из трех фаз, как и алгоритмы, описанные выше. Но на каждом уровне стягивания вычисляется раскраска графа. Эта раскраска используется для устранения конфликтов в вычислении глобального сочетания на фазе стягивания, а также для устранения лишних перемещений вершин при k-фазном уточнении, выполняемом на фазе уточнения. Поскольку вершины одного цвета образуют независимое множество, то эта схема гарантирует, что каждое перемещение вершины будет приводить к уменьшению количества разрезанных ребер. Кроме того, в алгоритме используется распараллеливание алгоритма начального разбиения графа для еще большего снижения уже и так малого времени выполнения этой фазы.

Пусть p - количество процессоров для вычисления р-фазного разбиения графа G = (V; E). G первоначально распределяется между процессорами, используя однонаправленное распределение так, что каждый процессор получает n=p вершин и списки их смежности. В конце алгоритма номер сегмента присваивается каждой вершине графа.

Раскраска графа. Раскраска графа G = (V; E) присваивает цвета вершинам графа G так, что смежные вершины имеют различные цвета. В ParMETIS ищется такая раскраска, чтобы количество отдельных используемых цветов было малым. Параллельный алгоритм раскраски, разработанный авторами ParMETIS, включает несколько итераций. В каждой итерации максимально независимое множество вершин I выбирается с использованием измененного алгоритма Луби (см. [15]). Всем вершинам в независимом множестве присваивается одинаковый цвет. Перед началом следующей операции вершины из множества I удаляются из графа, а образовавшийся меньший граф становится входным графом для следующей итерации. Максимально независимое множество I множества вершин S вычисляется в инкрементном порядке, используя алгоритм Луби следующим образом.

Каждой вершине присваивается случайное число, а если вершина получает случайный номер, который меньше, чем все номера смежных вершин, то эта вершина включается во множество I. После этого процесс повторяется для вершин из множества S, которые и не входят во множество I, и не являются смежными с вершинами из I, а I расширяется подобным образом. Это инкрементное наращивание множества I заканчивается тогда, когда больше нет вершин, которые могут быть вставлены в I. В [15] показано, что одна итерация алгоритма Луби требует всего O(log |S|) таких расширяющих шагов для поиска максимально независимого множества вершин из множества S.

В ParMETIS алгоритм Луби реализован для параллельной раскраски. В нем выполняется фаза установки соединения, в которой создаются структуры данных для помощи процесса обмена случайными номерами. В частности, в алгоритме предопределяется, какие вершины находятся на границе между процессорами, а какие являются внутренними вершинами. Эти структуры данных используются во всех фазах параллельного алгоритма разбиения графов.

Фаза огрубления (стягивания). Параллельный алгоритм стягивания основан на расширении последовательного алгоритма и использует раскраску графа для структуризации последовательности вычислений. Дан граф G_i = (V_i ; E_i), который был раскрашен с использованием параллельного алгоритма Луби. Пусть Match - это переменная, связанная с каждой вершиной графа, которое в начале имеет значение -1. В конце вычислений, переменная Match (Matсh это массив) для каждой вершины v содержит номер вершины, с которой вершина v должна быть стянута. Если v не стягивается, то Match = v. Значение M_i (это переменная Match_i или Match[i]) вычисляется итеративно. В течении c-й итерации, вершины цвета c, которые пока еще не были связаны (т.е., Match = -1), выбирают одного из своих несвязанных соседей, используя heavy-edge эвристику (т.е. эвристику "ребра тяжеловеса"), и модифицируют переменную Match выбранной вершины установкой в свои номера. Пусть v - вершина цвета c, а (v; u) - ребро, выбранное вершиной v. Поскольку цвет вершины u не c (расписываю - если вершина v имеет цвет c и связана ребром с вершиной u, то u не должно иметь цвет c, согласно постановке задачи раскрашивания графа), эта вершина (u - вершина; c - некоторый цвет) не будет выбирать себе партнера на данной итерации. Однако, есть возможность, что другая вершина w цвета c может выбрать ребро (w; u). Поскольку обе вершины v и w выполняют свой выбор одновременно (на одной и той же итерации), то такая ситуация не произойдет, потому что выбор происходит на одной и той же итерации; последовательно вершина v установит Match[u] := v, а потом вершина w установит Match[u] := w; последнее установленное значение будет использовано - смотреть следующие предложения. Это отрабатывается следующим образом. После того, как все вершины цвета c выберут несвязанных соседей, они синхронизируются. Вершины цвета c, которые только что выбрали соседа, читают значение переменной Match своей выбранной вершины. Если прочитанное значение равно их номеру вершины, то присоединение выполнено успешно, и они устанавливают свои переменные Match равными выбранной вершине; иначе присоединение считается неудавшимся, а вершина становится непривязанной. Следует отметить, что, если более чем одна вершина (например, v и w) хочет привязать к себе одну и туже вершину (например, u), то только одна из них успешно закончит присоединение; и это определяет, какие присоединения останутся. Однако, использование раскраски ограничивает выбор вершинами своих партнеров на каждой итерации. Так что, количество подобных конфликтных ситуаций значительно снижается. Также следует отметить, что даже если вершина цвета c может неудачно окончить присоединение из-за конфликтов, эта вершина все равно может быть присоединена в течении последующих итераций.

Фаза разбиения. В течение фазы разбиения, p-фазное разбиение вычисляется с использованием рекурсивного бисекционного алгоритма. Поскольку огрубленный граф имеет только O(p) вершин, этот шаг может быть выполнен последовательно (т.е., не параллельно), без значительного влияния на производительность всего алгоритма. Тем не менее, в ParMETIS эта фаза также распараллеливается с использованием рекурсивной декомпозиции. Это выполняется следующим образом: различные части грубого графа собираются на всех процессорах с использованием широковещательной операции. В этот момент процессоры выполняют рекурсивную бисекцию, используя алгоритм, основанный на вложенном рассечении (см. [16]) и жадном уточнении разбиения. Однако каждый процессор вырабатывает только один путь дерева рекурсивной бисекции. В конце каждый процессор накапливает вершины, которые соответствуют их сегментам p-фазного разбиения. Следует отметить, что после широковещательной операции, алгоритм работает без каких либо дополнительных коммуникаций между процессорами.

Фаза уточнения. На фазе уточнения, разбиение проецируется с грубого графа на следующий уровень детализированного графа и уточняется с использованием жадного алгоритма уточнения. В течение одной фазы уточнения в последовательном алгоритме выполняется проход по случайным вершинам, и они перемещаются в сегменты, что ведет к большему уменьшению разреза ребер. В параллельном исполнении жадного уточнения изменен порядок проверки вершин на предмет возможности их перемещения в другие сегменты. В частности, одна фаза алгоритма уточнения разбивается на c под-фаз, где c - это количество цветов уточняемого графа. В течение i-й фазы все вершины цвета i рассматриваются на возможность перемещения, а подмножество тех вершин, которые ведут к уменьшению количества разрезанных вершин, перемещаются. Т.к. вершины с одинаковым цветом образуют независимое множество, то общее уменьшение количества разрезанных ребер, полученное перемещением вершин в один и тот же момент времени, эквивалентно сумме уменьшений количества разрезанных ребер, получаемых перемещением этих вершин последовательно одна за другой. После выполнения этой группы перемещений внешние степени вершин, смежных с данной группой обновляются, а за тем обрабатывается следующий цвет.

В работе рассмотрены методы разбиения графов большой размерности со многими ограничениями, которые используются в пакетах METIS, ParMETIS и hMETIS. Установлено, что все эти пакеты используют модификации одного и того же алгоритма. Этот многоуровневый алгоритм состоит из трех фаз:
  - стягивание графа - для получения грубого уменьшенного графа;
  - начальное разбиение - получение разбиения уменьшенного графа;
  - уточнение - получение разбиения исходного графа путем последовательного проецирования разбиений на детализи- рованные графы каждого уровня, и путем уточнения разбиения на каждом уровне.

Пакет METIS использует последовательный алгоритм для разбиения графов. Пакет hMETIS использует тот же алгоритм, но модифицированный для поиска разбиений на гиперграфе. Пакет ParMETIS использует параллельный алгоритм разбиения, который похож на последовательный, но использует алгоритм раскраски графов, необходимый для предупреждения многих конфликтных ситуаций, вызываемых распараллеливанием.

список литературы

[1] George Karypis, Vipin Kumar. Multilevel Algorithms for Multi-Constraint Graph Partitioning. University of Minnesota, Department of Computer Science / Army HPC Research Center. Minneapolis, MN 55455. Technical Report # 98-019.

[2] George Karypis. Vipin Kumar. METIS. A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices Version 4.0. - University of Minnesota: September 20, 1998.

[3] G. Karypis and V. Kumar. A fast and highly quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 1998 (to appear). Also available on WWW at URL http://www.cs.umn.edu/?karypis. A short version appears in Intl. Conf. on Parallel Processing 1995.

[4] G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 48(1):96-129, 1998. Also available on WWW at URL http://www.cs.umn.edu/?karypis.

[5] Bruce Hendrickson and Robert Leland. The chaco user's guide, version 1.0. Technical Report SAND93-2339, Sandia National Laboratories, 1993.

[6] B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2):291-307, 1970.

[7] C. M. Fiduccia and R. M. Mattheyses. A linear time heuristic for improving network partitions. In In Proc. 19th IEEE Design Automation Conference, pages 175-181, 1982.

[8] Bruce Hendrickson and Robert Leland. A multilevel algorithm for partitioning graphs. Technical Report SAND93-1301, Sandia National Laboratories, 1993.

[9] George Karypis, Vipin Kumar. Multilevel k-way Hypergraph Partitioning. - Department of Computer Science & Engineering; Army HPC Research Center; University of Minnesota, Minneapolis, MN 55455. Technical Report #98-036.

[10] Charles J. Alpert and Andrew B. Kahng. Recent directions in netlist partitioning. Integration, the VLSI Journal, 19(1-2):1-81, 1995.

[11] C. M. Fiduccia and R. M. Mattheyses. A linear time heuristic for improving network partitions. In In Proc. 19th IEEE Design Automation Conference, pages 175-181, 1982.

[12] L. A. Sanchis. Multiple-way network partitioning. IEEE Transactions on Computers, pages 62-81, 1989.

[13] George Karypis, Kirk Schloegel and Vipin Kumar. PARMETIS Parallel Graph Partitioning and Sparse Matrix Ordering Library, Version 3.0. - University of Minnesota, Department of Computer Science and Engineering, Army HPC Research Center, Minneapolis, MN 55455: March 28, 2002.

[14] George Karypis, Vipin Kumar. Parallel Multilevel k-way Partitioning Scheme for Irregular Graphs. - University of Minnesota, Department of Computer Science / Army HPC Research Center, Minneapolis, MN 55455, Technical Report: 96-036.

[15] Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15(4):1036-1053, 1986.

[16] A. George. Nested dissection of a regular finite-element mesh. SIAM Journal on Numerical Ananlysis, 10:345-363, 1973.