Алгоритм Габова определения рёберной связности графа: различия между версиями
Перейти к навигации
Перейти к поиску
| [выверенная версия] | [досмотренная версия] |
ASA (обсуждение | вклад) |
ASA (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 21: | Строка 21: | ||
== Программная реализация алгоритма == | == Программная реализация алгоритма == | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
| − | |||
| − | |||
| − | |||
| − | |||
=== Возможные способы и особенности параллельной реализации алгоритма === | === Возможные способы и особенности параллельной реализации алгоритма === | ||
| − | === | + | === Результаты прогонов === |
| − | |||
| − | |||
| − | |||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
| − | |||
== Литература == | == Литература == | ||
| + | |||
<references /> | <references /> | ||
[[Категория:Начатые статьи]] | [[Категория:Начатые статьи]] | ||
| + | |||
| + | [[en:Gabow's edge connectivity algorithm]] | ||
Текущая версия на 17:55, 6 июля 2022
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Алгоритм Габова[1] предназначен для определения рёберной связности графов. Время работы алгоритма [math]O(k m \ln (n^2/m))[/math] для ориентированного и [math]O(m + k^2 n \ln (n/k))[/math] для неориентированного графа, где [math]k[/math] – рёберная связность. Проверка свойства [math]k[/math]-связности тем же алгоритмом может быть выполнена за время [math]O(m + n \ln n)[/math].
1.2 Математическое описание алгоритма
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
Время работы алгоритма [math]O(k m \ln (n^2/m))[/math] для ориентированного и [math]O(m + k^2 n \ln (n/k))[/math] для неориентированного графа, где [math]k[/math] – рёберная связность. Проверка свойства [math]k[/math]-связности тем же алгоритмом может быть выполнена за время [math]O(m + n \ln n)[/math].
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Возможные способы и особенности параллельной реализации алгоритма
2.3 Результаты прогонов
2.4 Выводы для классов архитектур
3 Литература
- ↑ Gabow, H N. “A Matroid Approach to Finding Edge Connectivity and Packing Arborescences.” Journal of Computer and System Sciences 50, no. 2 (April 1995): 259–73. doi:10.1006/jcss.1995.1022.
