电邮这篇文章 RASPREDELENNYY ALGORITM NUMERATsII VERShIN GRAFA, SOVMEShchENNYY S POSTROENIEM DEREVA OBKhODA V ShIRINU
- 作者: Kuznetsov O.P1
-
隶属关系:
- 期: 编号 11 (2025)
- 页面: 110-126
- 栏目: Optimization, system analysis, and operations research
- URL: https://bakhtiniada.ru/0005-2310/article/view/349855
- DOI: https://doi.org/10.31857/S0005231025110064
- ID: 349855
如何引用文章
开放存取
##reader.subscriptionAccessGranted##
订阅存取
详细
Предлагается новый распределенный алгоритм нумерации вершин корневого неориентированного графа, который в процессе нумерации строит остовное дерево, являющееся при этом деревом обхода в ширину. Приведены оценки сложности алгоритма.
参考
- Левеиштейн В.И. Об одном методе решения задачи синхронизации цепи автоматов за минимальное время // Пробл. передачи информ. 1965. Т. 1. Вып. 4. С. 20–32.
- Moore F.R., Langdon G.G. A generalized firing squad problem // Information and Control. 1968. V. 12. P. 212–220.
- 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.
- 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.
- Вальой М.Н., Хузиев И.М. Распределенная коммуникационная сложность построения остовного дерева // Пробл. передачи информ. 2015. Т. 51. № 1. С. 54–71.
- Вальой М.Н., Хузиев И.М. Быстрые протоколы выбора лидера и построения остовного дерева в распределенной сети // Пробл. передачи информ. 2017. Т. 53. № 2. С. 91–111.
- Dinitz M., Halldorsson M., Izumi T., Newport C. Distributed minimum degree spanning trees // Proceedings 2019 ACM Symposium Principles Distributed Computing, 2019. P. 511–520.
- Auerbuch B., Gallagher R.G. Distributed BFS algorithms // Proc. 26 IEEE Symposium Foundations Computer Science (FOCS). 1985. P. 250–255.
- 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.
- Makki S.A.M. Efficient distributed breadth-first algorithm // Computer Communications. 1996. V. 19. No. 8. P. 628–636.
- Бурдонов И., Косачев А. Общий подход к решению задач на графах коллективом автоматов // Труды ИСП РАН. 2017. Т. 29. Вып. 2. С. 27–76.
- Бурдонов И., Косачев А., Сортов А. Распределённые алгоритмы на корневых неориентированных графах // Труды ИСП РАН, 2017. Т. 29. Вып. 5. С. 283–310.
- Ghaffari M. Distributed Graph Algorithms. 2022. https://people.csail.mit.edu/ghaffari/DA22/Notes/DGA.pdf
- Ope O. Теория графов. М.: Наука. 1968.
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦНМО. 2001.
- 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.
补充文件
