РАСПРЕДЕЛЕННЫЙ АЛГОРИТМ НУМЕРАЦИИ ВЕРШИН ГРАФА, СОВМЕЩЕННЫЙ С ПОСТРОЕНИЕМ ДЕРЕВА ОБХОДА В ШИРИНУ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

Предлагается новый распределенный алгоритм нумерации вершин корневого неориентированного графа, который в процессе нумерации строит остовное дерево, являющееся при этом деревом обхода в ширину. Приведены оценки сложности алгоритма.

Об авторах

О. П Кузнецов

Институт проблем управления им. В.А. Трапезникова РАН

Email: olpkuz@yandex.ru
д-р техн. наук Москва

Список литературы

  1. Левеиштейн В.И. Об одном методе решения задачи синхронизации цепи автоматов за минимальное время // Пробл. передачи информ. 1965. Т. 1. Вып. 4. С. 20–32.
  2. Moore F.R., Langdon G.G. A generalized firing squad problem // Information and Control. 1968. V. 12. P. 212–220.
  3. Gallager R.G., Humblet P.A., Spira P.M. A distributed algorithm for minimum-weight spanning trees // ACM Transactions on Programming Languages and Systems. 1983. V. 5. No. 1. P. 66–77.
  4. Peleg D., Rubinovich V. A near-tight lower bound on the time complexity of distributed MST construction // Proc. 40 IEEE Symp. on Found. of Comp. Sci. (FOCS). 1999. P. 253–261.
  5. Вальой М.Н., Хузиев И.М. Распределенная коммуникационная сложность построения остовного дерева // Пробл. передачи информ. 2015. Т. 51. № 1. С. 54–71.
  6. Вальой М.Н., Хузиев И.М. Быстрые протоколы выбора лидера и построения остовного дерева в распределенной сети // Пробл. передачи информ. 2017. Т. 53. № 2. С. 91–111.
  7. Dinitz M., Halldorsson M., Izumi T., Newport C. Distributed minimum degree spanning trees // Proceedings 2019 ACM Symposium Principles Distributed Computing, 2019. P. 511–520.
  8. Auerbuch B., Gallagher R.G. Distributed BFS algorithms // Proc. 26 IEEE Symposium Foundations Computer Science (FOCS). 1985. P. 250–255.
  9. Park J., Tokura N., Masuzawa T., Hagihara K. An efficient distributed algorithm for constructing a breadth-first search tree // Systems and Computers in Japan. 1989. V. 20. P. 15–30.
  10. Makki S.A.M. Efficient distributed breadth-first algorithm // Computer Communications. 1996. V. 19. No. 8. P. 628–636.
  11. Бурдонов И., Косачев А. Общий подход к решению задач на графах коллективом автоматов // Труды ИСП РАН. 2017. Т. 29. Вып. 2. С. 27–76.
  12. Бурдонов И., Косачев А., Сортов А. Распределённые алгоритмы на корневых неориентированных графах // Труды ИСП РАН, 2017. Т. 29. Вып. 5. С. 283–310.
  13. Ghaffari M. Distributed Graph Algorithms. 2022. https://people.csail.mit.edu/ghaffari/DA22/Notes/DGA.pdf
  14. Ope O. Теория графов. М.: Наука. 1968.
  15. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦНМО. 2001.
  16. Mettrier Y., Robson J.M., Zemmari A. A distributed enumeration algorithm and applications to all pairs shortest paths, diameter…// Information and Computation. 2016. V. 247. P. 141–151.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2025