Алгоритм Габова определения рёберной связности графа - История изменений

ASA в 14:55, 6 июля 2022

2022-07-06T14:55:11Z

← Предыдущая версия		Версия от 14:55, 6 июля 2022
Строка 21:		Строка 21:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	~~=== Локальность данных и вычислений ===~~
	~~==== Локальность реализации алгоритма ====~~
	~~===== Структура обращений в память и качественная оценка локальности =====~~
	~~===== Количественная оценка локальности =====~~
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== ~~Масштабируемость алгоритма и его реализации ===~~		=== Результаты прогонов ===
	~~==== Масштабируемость алгоритма ====~~
	~~==== Масштабируемость реализации алгоритма ====~~
	~~=== Динамические характеристики и эффективность реализации алгоритма~~ ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	~~=== Существующие реализации алгоритма ===~~

	== Литература ==		== Литература ==

	<references />		<references />

ASA в 14:00, 14 марта 2018

2018-03-14T14:00:59Z

← Предыдущая версия		Версия от 14:00, 14 марта 2018
Строка 37:		Строка 37:

	[[Категория:Начатые статьи]]		[[Категория:Начатые статьи]]

			[[en:Gabow's edge connectivity algorithm]]

ASA в 14:19, 6 марта 2018

2018-03-06T14:19:38Z

← Предыдущая версия		Версия от 14:19, 6 марта 2018
Строка 1:		Строка 1:
			{{level-a}}

	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

ASA в 11:30, 29 июля 2015

2015-07-29T11:30:17Z

← Предыдущая версия		Версия от 11:30, 29 июля 2015
Строка 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 />

	~~<references />~~		[[Категория:Начатые статьи]]

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

2015-06-07T21:11:37Z

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

Новая страница

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

'''Алгоритм Габова'''<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>.

=== Математическое описание ===
=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
=== Описание схемы реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===

Время работы алгоритма <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>.

=== Информационный граф ===
=== Описание ресурса параллелизма алгоритма ===
=== Описание входных и выходных данных ===
=== Свойства алгоритма===
== Программная реализация алгоритмов ==
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
=== Возможные способы и особенности реализации параллельного алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
== Литература ==

<references />