Universally-Optimal Distributed Exact Min-Cut
Mohsen Ghaffari, Goran Žužić
Abstract
We present a universally-optimal distributed algorithm for the exact weighted min-cut. The algorithm is guaranteed to complete in Õ(D + √n ) rounds on every graph, recovering the recent result of Dory, Efron, Mukhopadhyay, and Nanongkai [STOC'21], but runs much faster on structured graphs. Specifically, the algorithm completes in Õ(D) rounds on (weighted) planar graphs or, more generally, any (weighted) excluded-minor family.
Topics & Concepts
CombinatoricsMaximum cutComputer scienceMathematicsDistributed algorithmDiscrete mathematicsAlgorithmGraphDistributed computingComplexity and Algorithms in GraphsCryptography and Data SecurityPrivacy-Preserving Technologies in Data