Massively parallel algorithms for minimum cut

03/08/2020

Massively parallel algorithms for minimum cut

Mohsen Ghaffari, Krzysztof Nowicki

Keywords: massively parallel computation, minimum cut, congested clique, random contraction, MapReduce algorithms

Abstract: We present two Massively Parallel Computation (MPC) algorithms for the Minimum Cut problem: an O(1)-round exact algorithm with Õ(n) memory per machine, and an O(log n · log log n) round (2 + ε) approximation with Õ(nα) memory per machine, for any positive constant α < 1. Both algorithms use Õ(m) global memory.

PODC

This is an embedded video. Talk and the respective paper are published at PODC 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment

no comments yet