Efficient massively parallel graph coloring algorithms via transformations from distributed local algorithms
- 講者張以潤 先生 (密西根大學)
邀請人：鐘楷閔 - 時間2019-06-14 (Fri.) 10:00 ~ 12:00
- 地點資訊所新館106演講廳
摘要
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)