Lower and Upper Bound on Computational of Diameter in Distributed Networks

Lower and Upper Bound on Computational of Diameter in Distributed Networks

Date:

Monday, September 12, 2016 - 15:00

Abstract:

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