Massively Parallel Algorithms for Minimum Cut

descriptionPublicationkeyboard_double_arrow_right Article , Conference object 31 Jul 2020Publisher:ACMJournal:Proceedings of the 39th Symposium on Principles of Distributed ComputingFunded by:EC | DistMaP

Authors: Ghaffari, Mohsen; Nowicki, Krzysztof;

doi: 10.1145/3382734.3405737

handle: 20.500.11850/440141

Massively Parallel Algorithms for Minimum Cut

- Summary
- Subjects
- Metrics

Abstract

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

Related Organizations

ETH Zurich
Switzerland
University of Wrocław
Poland

Keywords

Massively parallel computation; MapReduce algorithms; Minimum cut; Congested clique; Random contraction

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	7
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average