Вычислительные методы и программирование
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Выч. мет. программирование:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Выч. мет. программирование, 2014, том 15, выпуск 3, страницы 400–410 (Mi vmp259)  

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

А. С. Русаков, М. В. Шеблаев

Институт проблем проектирования в микроэлектронике РАН

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

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

Полный текст: PDF файл (235 kB)
Тип публикации: Статья
УДК: 519.658; 519.677; 519.176
Поступила в редакцию: 02.06.2014

Образец цитирования: А. С. Русаков, М. В. Шеблаев, “Оптимизация алгоритма разбиения гиперграфа с произвольными весами вершин”, Выч. мет. программирование, 15:3 (2014), 400–410

Цитирование в формате AMSBIB
\RBibitem{RusShe14}
\by А.~С.~Русаков, М.~В.~Шеблаев
\paper Оптимизация алгоритма разбиения гиперграфа с произвольными весами вершин
\jour Выч. мет. программирование
\yr 2014
\vol 15
\issue 3
\pages 400--410
\mathnet{http://mi.mathnet.ru/vmp259}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vmp259
  • http://mi.mathnet.ru/rus/vmp/v15/i3/p400

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Вычислительные методы и программирование
    Просмотров:
    Эта страница:168
    Полный текст:71
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021