Определение вершинной связности графа

Материал из Алговики
Перейти к навигации Перейти к поиску

Содержание

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Алгоритм Хенцингер-Рао-Габова[1] предназначен для определения вершинной связности графа. Время работы для ориентированного графа [math]O(\min \{ k^3 + n, kn \} m)[/math], где [math]k[/math] – вершинная связность. Для неориентированного графа множитель [math]m[/math] может быть заменён на [math]kn[/math]. В основе алгоритма лежат идеи из более ранних работ[2][3][4][5]: задача о поиске вершинной связности графа может быть сведена к последовательности задач на максимальный поток в нагруженном графе.

1.2 Математическое описание алгоритма

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

Последовательная сложность алгоритма Хенцигер-Рао-Габова для ориентированного графа [math]O(\min \{ k^3 + n, kn \} m)[/math], где [math]k[/math] – вершинная связность. Для неориентированного графа множитель [math]m[/math] может быть заменён на [math]kn[/math].

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

  1. Henzinger, Monika R, Satish Rao, and Harold N Gabow. “Computing Vertex Connectivity: New Bounds From Old Techniques.” Journal of Algorithms 34, no. 2 (February 2000): 222–50. doi:10.1006/jagm.1999.1055.
  2. Even, Shimon, and R Endre Tarjan. “Network Flow and Testing Graph Connectivity.” SIAM Journal on Computing 4, no. 4 (1975): 507–18. doi:10.1137/0204043.
  3. Even, Shimon. “An Algorithm for Determining Whether the Connectivity of a Graph Is at Least K.” SIAM Journal on Computing 4, no. 3 (1975): 393–96.
  4. Galil, Zvi. “Finding the Vertex Connectivity of Graphs.” SIAM Journal on Computing 9, no. 1 (February 1980): 197–99. doi:10.1137/0209016.
  5. Hao, J X, and J B Orlin. “A Faster Algorithm for Finding the Minimum Cut in a Directed Graph.” Journal of Algorithms 17, no. 3 (November 1994): 424–46. doi:10.1006/jagm.1994.1043.