RASPREDELENNYY ALGORITM NUMERATsII VERShIN GRAFA, SOVMEShchENNYY S POSTROENIEM DEREVA OBKhODA V ShIRINU

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

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

About the authors

O. P Kuznetsov

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

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

References

  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.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Russian Academy of Sciences