Massively parallel algorithms for finding connected components

Prelegent(ci)

Jakub Łącki

Afiliacja

Google Research NY

Termin

19 grudnia 2019 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

In this talk we consider the problem of finding connected components in a distributed setting. We present state of the art algorithms that achieve near-optimal round complexity and work well in practice. Our main focus is the Massively Parallel Computation (MPC) model, which is the standard theoretical model for modern parallel frameworks such as MapReduce, Hadoop, or Spark. This is joint work with Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Vahab Mirrokni, Warren Schudy and Michał Włodarczyk.

---