Lower and Upper Bound on Computational of Diameter in Distributed Networks

Lower and Upper Bound on Computational of Diameter in Distributed Networks

Дата:

Monday, September 12, 2016 - 15:00

Аннотация:

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