Оптимизация алгоритма разбиения гиперграфа с произвольными весами вершин
Русаков А.С., Шеблаев М.В.

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

Ключевые слова: разбиение гиперграфа, FM-алгоритм, кластеризация, распределенные вычислительные системы, параллельное программирование.

Название статьи, аннотация и ключевые слова на английском языке

  • Русаков А.С. – Институт проблем проектирования в микроэлектронике РАН, ул. Советская, д. 3, 124365, Зеленоград; ст. науч. сотр., e-mail: rusakov@inm.ras.ru
  • Шеблаев М.В. – Институт проблем проектирования в микроэлектронике РАН, ул. Советская, д. 3, 124365, Зеленоград; науч. сотр., e-mail: sheblaev@gmail.com