Д. И. Батищев, Н. В. Старостин, А. В. Филимонов Многоуровневая декомпозиция гиперграфовых структур

---

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

Batischev D. L, Starostin N. V., Elimonov A. V.
Multilevel hypergraph partitioning

      This paper presents a multilevel partitioning method for hypergraph models. Basics of hypergraph theory are under consideration as well as related topics such as hypergraph visualization. The concept of weighted hypergraph is extended by introducing attributes, a number of new operations so-called ╚filtering operations╩ are defined in this connection. Partitioning problem is formulated, multilevel paradigm is suggested as a method of solving partitioning problems of high dimension. Steps and levels of multilevel algorithms are canvassed, applications of evolutional computations to multilevel methods are considered. The results of computing experiments are exposed.



СОДЕРЖАНИЕ


Введение
1. Основные определения и понятия гиперграфовых структур
2. Визуализация гиперграфа
3. Части гиперграфа и связность
4. Базовые операции над гиперграфом
5. Атрибуты, операции фильтрации и фильтры
6. Типы фильтров
7. Атрибутивная связность между гиперграфами
8. Постановка задачи и многоуровневая декомпозиция
9. Алгоритмическое обеспечение
     9.1. Алгоритм реберного загрубления
     9.2. Схема гиперреберного загрубления
     9.3. Алгоритм построения затрубленного гиперграфа
     9.4. Алгоритмы поиска начального разбиения
     9.5. Фаза восстановления решений
10. Использование концепции "фильтр-вид" для построения многоуровневого алгоритма декомпозиции
     10.1. Фаза загрубления
     10.2. Фаза восстановления решений
11. Многоуровневый алгоритм с элементами эволюционно-генетического поиска
12. Вычислительный эксперимент
Заключение
Список литературы