- PII
- S24139777S0005231025110064-1
- DOI
- 10.7868/S2413977725110064
- Publication type
- Article
- Status
- Published
- Authors
- Volume/ Edition
- Volume / Issue number 11
- Pages
- 110-126
- Abstract
- Предлагается новый распределенный алгоритм нумерации вершин корневого неориентированного графа, который в процессе нумерации строит остовное дерево, являющееся при этом деревом обхода в ширину. Приведены оценки сложности алгоритма.
- Keywords
- Date of publication
- 01.11.2025
- Year of publication
- 2025
- Number of purchasers
- 0
- Views
- 15
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.
