Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 19, 2021, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Christoph Grunau
Network decomposition is a central tool in distributed graph algorithms. Rozhoň and Ghaffari presented the first deterministic CONGEST algorithm for network decomposition running in a polylogarithmic number of rounds [STOC'20]. The O(log^8 n) round complexity of their algorithm was subsequently improved to O(log^5 n) by Ghaffari, Grunau and Rozhoň [SODA' 21]. Both of the aforementioned results compute a so-called weak-diameter network decomposition, as opposed to the stronger notion of a strong-diameter network decomposition. Recently, Chang and Ghaffari devised an algorithm that computes a strong-diameter network decomposition in O(log^8 n) rounds [PODC' 21]. In this talk, I present a CONGEST algorithm that computes a strong-diameter network decomposition in O(log^5 n) rounds, which matches the round complexity of the currently fastest weak-diameter network decomposition algorithm. This is joint work together with Bernhard Haeupler and Vaclav Rozhoň.
Automatic MiSe System Software Version 1.4803M | admin login