Алгоритм Габова определения рёберной связности графа: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) Общее описание алгоритма |
ASA (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
== Свойства и структура | == Свойства и структура алгоритма == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
'''Алгоритм Габова'''<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: | Строка 13: | ||
=== Информационный граф === | === Информационный граф === | ||
=== | === Ресурс параллелизма алгоритма === | ||
=== | === Входные и выходные данные алгоритма === | ||
=== Свойства алгоритма=== | === Свойства алгоритма === | ||
== Программная реализация | |||
== Программная реализация алгоритма == | |||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
=== | === Локальность данных и вычислений === | ||
=== Возможные способы и особенности реализации | ==== Локальность реализации алгоритма ==== | ||
===== Структура обращений в память и качественная оценка локальности ===== | |||
===== Количественная оценка локальности ===== | |||
=== Возможные способы и особенности параллельной реализации алгоритма === | |||
=== Масштабируемость алгоритма и его реализации === | === Масштабируемость алгоритма и его реализации === | ||
==== Масштабируемость алгоритма ==== | |||
==== Масштабируемость реализации алгоритма ==== | |||
=== Динамические характеристики и эффективность реализации алгоритма === | === Динамические характеристики и эффективность реализации алгоритма === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
== Литература == | == Литература == | ||
<references /> | |||
[[Категория:Начатые статьи]] | |||
Версия от 11:30, 29 июля 2015
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм Габова[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.