• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Распределенная коммуникационная сложность построения остовного дерева

Проблемы передачи информации. 2015. Т. 51. № 1. С. 54-71.
Вялый М. Н., Хузиев И. М.
We consider the problem of constructing a spanning tree in a synchronized network with an unknown topology. We give lower and upper bounds on the complexity of protocols for spanning tree constriction in various settings: for deterministic and probabilistic protocols, networks with distinguishable nodes, and anonymous networks. We present suboptimal protocols for which the multiplicative gap from the lower bound can be an arbitrarily slowly growing function of the number of vertices in the network.