Оптимизация алгоритма разбиения гиперграфа с произвольными весами вершин

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