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

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

2022-07-06T14:54:03Z

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

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

	<references />		<references />

ASA в 13:59, 14 марта 2018

2018-03-14T13:59:51Z

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

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

			[[en:Vertex connectivity of a graph]]

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

2018-03-06T14:19:21Z

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

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

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

2015-07-29T11:29:35Z

← Предыдущая версия		Версия от 11:29, 29 июля 2015
Строка 1:		Строка 1:
	== Свойства и структура ~~алгоритмов~~ ==		== Свойства и структура алгоритма ==

	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
Строка 5:		Строка 5:
	'''Алгоритм Хенцингер-Рао-Габова'''<ref>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.</ref> предназначен для определения [[Связность в графах\|вершинной связности]] графа. Время работы для ориентированного графа <math>O(\min \{ k^3 + n, kn \} m)</math>, где <math>k</math> – вершинная связность. Для неориентированного графа множитель <math>m</math> может быть заменён на <math>kn</math>. В основе алгоритма лежат идеи из более ранних работ<ref>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.</ref><ref>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.</ref><ref>Galil, Zvi. “Finding the Vertex Connectivity of Graphs.” SIAM Journal on Computing 9, no. 1 (February 1980): 197–99. doi:10.1137/0209016.</ref><ref>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.</ref>: задача о поиске вершинной связности графа может быть сведена к последовательности задач [[Поиск максимального потока в нагруженном графе\|на максимальный поток в нагруженном графе]].		'''Алгоритм Хенцингер-Рао-Габова'''<ref>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.</ref> предназначен для определения [[Связность в графах\|вершинной связности]] графа. Время работы для ориентированного графа <math>O(\min \{ k^3 + n, kn \} m)</math>, где <math>k</math> – вершинная связность. Для неориентированного графа множитель <math>m</math> может быть заменён на <math>kn</math>. В основе алгоритма лежат идеи из более ранних работ<ref>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.</ref><ref>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.</ref><ref>Galil, Zvi. “Finding the Vertex Connectivity of Graphs.” SIAM Journal on Computing 9, no. 1 (February 1980): 197–99. doi:10.1137/0209016.</ref><ref>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.</ref>: задача о поиске вершинной связности графа может быть сведена к последовательности задач [[Поиск максимального потока в нагруженном графе\|на максимальный поток в нагруженном графе]].

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

Строка 14:		Строка 14:

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

	== Литература ==		== Литература ==
			<references />

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

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

2015-06-08T22:07:43Z

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

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

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

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

'''Алгоритм Хенцингер-Рао-Габова'''<ref>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.</ref> предназначен для определения [[Связность в графах|вершинной связности]] графа. Время работы для ориентированного графа <math>O(\min \{ k^3 + n, kn \} m)</math>, где <math>k</math> – вершинная связность. Для неориентированного графа множитель <math>m</math> может быть заменён на <math>kn</math>. В основе алгоритма лежат идеи из более ранних работ<ref>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.</ref><ref>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.</ref><ref>Galil, Zvi. “Finding the Vertex Connectivity of Graphs.” SIAM Journal on Computing 9, no. 1 (February 1980): 197–99. doi:10.1137/0209016.</ref><ref>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.</ref>: задача о поиске вершинной связности графа может быть сведена к последовательности задач [[Поиск максимального потока в нагруженном графе|на максимальный поток в нагруженном графе]].

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

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

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

<references />