# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

__Mittagsseminar Talk Information__ | |

**Date and Time**: Tuesday, October 19, 2021, 12:15 pm

**Duration**: 30 minutes

**Location**: OAT S15/S16/S17

**Speaker**: Christoph Grunau

## Improved CONGEST Algorithm for Strong-Diameter Network Decomposition

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ň.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login