Efficient massively parallel graph coloring algorithms via transformations from distributed local algorithms
- LecturerMr. Yi-Jun Chang (Department of EECS, University of Michigan)
Host: Kai-Min Chung - Time2019-06-14 (Fri.) 10:00 ~ 12:00
- LocationAuditorium106 at IIS new Building
Abstract
The Massively Parallel Computation (MPC) model was introduced recently as a theoretical abstraction for practical large-scale parallel processing settings such as MapReduce, Hadoop, Spark, and Dryad, and it has been receiving increasing more attention over the past few years. In this talk, we will discuss a method for transforming distributed local algorithms into efficient parallel algorithms, and how this approach leads to efficient graph coloring algorithms in the MPC model and some other related computation models. The talk will be mainly based on this paper: 【The Complexity of (Δ+1)Coloring inCongested Clique, Massively Parallel Computation,and Centralized Local Computation】 (PODC 2019)