Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 22, 2019, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Manuela Fischer
We present a simple graph partitioning algorithm for the (Δ+1)-vertex-coloring problem in three well-studied models of distributed, parallel, and centralized computation. More concretely, our graph partitioning leads to an O(1)-round algorithm in the congested clique, improving over the O(log* Δ)-round algorithm by Parter and Su [DISC'18], as well as an O(log log log n)-round algorithm in the massively parallel computation model with strongly sublinear memory and a centralized local computation algorithm with poly(Δ)log n queries.
Automatic MiSe System Software Version 1.4803M | admin login