Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 07, 2019, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Jara Uitto
The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale parallel computation frameworks and has recently gained a lot of importance, especially in the context of classic graph problems. Unsatisfactorily, all current poly(log log n)-round MPC algorithms seem to get fundamentally stuck at the linear-memory barrier: their efficiency crucially relies on each machine having space at least linear in the number n of nodes. In this talk, we study the maximal matching and the maximal independent set problems in the MPC model with truly sublinear memory per machine. For the case of graphs with arboricity bounded by \lambda, we show algorithms with runtime O(log \lambda \cdot log log \lambda + (log log n)^2).
Automatic MiSe System Software Version 1.4803M | admin login