Lower and Upper Bound on Computational of Diameter in Distributed Networks

Докладчик: 
Николай Карпов (ПОМИ)
Дата: 
Monday, September 12, 2016 - 15:00
Место: 
ПОМИ, ауд. 402
Аннотация: 

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