Алгоритм Габова определения рёберной связности графа: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [досмотренная версия] |
Daryin (обсуждение | вклад) Общее описание алгоритма |
ASA (обсуждение | вклад) Нет описания правки |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
== Свойства и структура | {{level-a}} | ||
== Свойства и структура алгоритма == | |||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
'''Алгоритм Габова'''<ref>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.</ref> предназначен для определения [[Связность в графах|рёберной связности]] графов. Время работы алгоритма <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>. | '''Алгоритм Габова'''<ref>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.</ref> предназначен для определения [[Связность в графах|рёберной связности]] графов. Время работы алгоритма <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>. | ||
=== Математическое описание === | === Математическое описание алгоритма === | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
=== | === Схема реализации последовательного алгоритма === | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| Строка 13: | Строка 15: | ||
=== Информационный граф === | === Информационный граф === | ||
=== | === Ресурс параллелизма алгоритма === | ||
=== | === Входные и выходные данные алгоритма === | ||
=== Свойства алгоритма=== | === Свойства алгоритма === | ||
== Программная реализация | |||
== Программная реализация алгоритма == | |||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
=== Возможные способы и особенности параллельной реализации алгоритма === | |||
=== Возможные способы и особенности реализации | === Результаты прогонов === | ||
=== | |||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
[[Категория:Начатые статьи]] | |||
[[en:Gabow's edge connectivity algorithm]] | |||
Текущая версия от 14:55, 6 июля 2022
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм Габова[1] предназначен для определения рёберной связности графов. Время работы алгоритма [math]\displaystyle{ O(k m \ln (n^2/m)) }[/math] для ориентированного и [math]\displaystyle{ O(m + k^2 n \ln (n/k)) }[/math] для неориентированного графа, где [math]\displaystyle{ k }[/math] – рёберная связность. Проверка свойства [math]\displaystyle{ k }[/math]-связности тем же алгоритмом может быть выполнена за время [math]\displaystyle{ O(m + n \ln n) }[/math].
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Время работы алгоритма [math]\displaystyle{ O(k m \ln (n^2/m)) }[/math] для ориентированного и [math]\displaystyle{ O(m + k^2 n \ln (n/k)) }[/math] для неориентированного графа, где [math]\displaystyle{ k }[/math] – рёберная связность. Проверка свойства [math]\displaystyle{ k }[/math]-связности тем же алгоритмом может быть выполнена за время [math]\displaystyle{ O(m + n \ln n) }[/math].
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Возможные способы и особенности параллельной реализации алгоритма
Результаты прогонов
Выводы для классов архитектур
Литература
- ↑ 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.