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

Мұқаба

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Рұқсат ақылы немесе тек жазылушылар үшін

Аннотация

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

Авторлар туралы

O. Kuznetsov

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

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
Жүктеу

© Russian Academy of Sciences, 2025