Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, May 24, 2018, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Manuela Fischer
Recently, studying fundamental graph problems in the Massively Parallel Computation (MPC) framework, inspired by the MapReduce paradigm, has gained a lot of attention. A standard assumption, common to most traditional approaches, is to allow memory which is linear in the number n of nodes in the graph. However, as pointed out by Karloff et al. [SODA'10] and Czumaj et al. [arXiv:1707.03478], this might be unrealistic for real-world graphs.
We propose the study of a more practical variant of the MPC model which only requires substantially sublinear or even subpolynomial memory per machine. In contrast to the standard MPC model and also to the streaming model, in this low-memory MPC setting a single machine will never see all the nodes in the graph. We introduce a new technique to cope with this imposed locality.
In particular, we show that the Maximal Independent Set (MIS) problem can be solved efficiently, that is, in O(log3 log n) rounds, when the input graph is a tree. This substantially reduces the local memory from almost linear required by the recent O(log log n)-round MIS algorithm of Ghaffari et al. [PODC'18] to nε, and exponentially improves on the O(sqrt(log n) log log n)-algorithm by Lenzen and Wattenhofer [PODC'11] which can cope with sublinear memory.
Automatic MiSe System Software Version 1.4803M | admin login