Алгоритм GHS: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [досмотренная версия] |
Daryin (обсуждение | вклад) Общее описание алгоритма |
ASA (обсуждение | вклад) Нет описания правки |
||
| (не показаны 4 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
== Свойства и структура | {{level-a}} | ||
== Свойства и структура алгоритма == | |||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
Алгоритм GHS (Gallager, Humblet, Spira)<ref>Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.</ref> предназначен для распределённого [[Построение минимального остовного дерева (MST)|построения минимального остовного дерева]] во взвешенном неориентированном графе. Алгоритм GHS основан на [[алгоритм Борувки|алгоритме Борувки]], адаптированном для применения в распределённой среде. Известны модификации алгоритма, улучшающие среднее и наихудшее время работы<ref>Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.</ref><ref>Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.</ref><ref>Garay, Juan A, Shay Kutten, and David Peleg. “A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees.” SIAM Journal on Computing 27, no. 1 (February 1998): 302–16. doi:10.1137/S0097539794261118.</ref><ref>Faloutsos, Michalis, and Mart Molle. “A Linear-Time Optimal-Message Distributed Algorithm for Minimum Spanning Trees.” Distributed Computing 17, no. 2 (August 2004). doi:10.1007/s00446-004-0107-2.</ref>. | '''Алгоритм GHS''' (сокр. от фамилий авторов: Gallager, Humblet, Spira)<ref>Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.</ref> предназначен для распределённого [[Построение минимального остовного дерева (MST)|построения минимального остовного дерева]] во взвешенном неориентированном графе. Алгоритм GHS основан на [[алгоритм Борувки|алгоритме Борувки]], адаптированном для применения в распределённой среде. Известны модификации алгоритма, улучшающие среднее и наихудшее время работы<ref>Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.</ref><ref>Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.</ref><ref>Garay, Juan A, Shay Kutten, and David Peleg. “A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees.” SIAM Journal on Computing 27, no. 1 (February 1998): 302–16. doi:10.1137/S0097539794261118.</ref><ref>Faloutsos, Michalis, and Mart Molle. “A Linear-Time Optimal-Message Distributed Algorithm for Minimum Spanning Trees.” Distributed Computing 17, no. 2 (August 2004). doi:10.1007/s00446-004-0107-2.</ref>. | ||
=== Математическое описание === | === Математическое описание алгоритма === | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
=== | === Схема реализации последовательного алгоритма === | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
=== Информационный граф === | === Информационный граф === | ||
=== | === Ресурс параллелизма алгоритма === | ||
=== | === Входные и выходные данные алгоритма === | ||
=== Свойства алгоритма=== | === Свойства алгоритма === | ||
== Программная реализация | |||
== Программная реализация алгоритма == | |||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
=== Возможные способы и особенности параллельной реализации алгоритма === | |||
=== Возможные способы и особенности реализации | === Результаты прогонов === | ||
=== | |||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
[[Категория:Начатые статьи]] | |||
[[en:GHS algorithm]] | |||
Текущая версия от 07:23, 7 июля 2022
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм GHS (сокр. от фамилий авторов: Gallager, Humblet, Spira)[1] предназначен для распределённого построения минимального остовного дерева во взвешенном неориентированном графе. Алгоритм GHS основан на алгоритме Борувки, адаптированном для применения в распределённой среде. Известны модификации алгоритма, улучшающие среднее и наихудшее время работы[2][3][4][5].
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Возможные способы и особенности параллельной реализации алгоритма
Результаты прогонов
Выводы для классов архитектур
Литература
- ↑ Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.
- ↑ Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.
- ↑ Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.
- ↑ Garay, Juan A, Shay Kutten, and David Peleg. “A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees.” SIAM Journal on Computing 27, no. 1 (February 1998): 302–16. doi:10.1137/S0097539794261118.
- ↑ Faloutsos, Michalis, and Mart Molle. “A Linear-Time Optimal-Message Distributed Algorithm for Minimum Spanning Trees.” Distributed Computing 17, no. 2 (August 2004). doi:10.1007/s00446-004-0107-2.