Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, November 14, 2019, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Daan Nilis
We present an algorithm to find a (2+\epsilon)-approximate minimum weight vertex cover in the Massively Parallel Computation model where each machine has near linear memory w.r.t. the number of vertices in the graph. Our algorithm has a round complexity of O(log log d) where d is the average degree of the graph. This result indicates that the weighted version can be solved as fast as the unweighted version by Ghaffari et al. [PODC’18]. Joint work with Mohsen Ghaffari.
Automatic MiSe System Software Version 1.4803M | admin login