• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

Проблемы передачи информации. 2015. Т. 51. № 1. С. 54-71.
Вялый М. Н., Хузиев И. М.

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