Answers are grounded in this paper and cite their sources.
We present the first near-linear work and poly-logarithmic depth algorithm for computing a minimum cut in an undirected graph. Previous parallel algorithms with poly-logarithmic depth required at least quadratic work in the number of vertices. In a graph with n vertices and m edges, our randomized algorithm computes the minimum cut with high probability in O ( m log 4 n ) work and O (log 3 n ) depth. This result is obtained by parallelizing a data structure that aggregates weights along paths in a tree, in addition exploiting the connection between minimum cuts and approximate maximum packings of spanning trees. In addition, our algorithm improves upon bounds on the number of cache misses incurred to compute a minimum cut.
No takes yet. Share an insight, caveat, or question.
Geissmann et al. (2021) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: