Brief announcement: almost-tight approximation distributed algorithm for minimum cut

In this short paper, we present an improved algorithm for approximating the minimum cut on dis-tributed (CONGEST) networks. Let λ be the minimum cut. Our algorithm can compute λ exactly in Õ(( n + D) poly(λ)) time, where n is the number of nodes (processors) in the network, D is the net-work diameter, and O ̃ hides poly log n. By a standard reduction, we can convert this algorithm into a (1+ )-approximation Õ(( n+D)/poly())-time algorithm. The latter result improves over the previ