A Parallel Min-Cut Algorithm using Iteratively Reweighted Least Squares
Yao Lin Zhu, David F. Gleich · arXiv (Cornell University) · 2015
We present a parallel algorithm for the undirected $s,t$-mincut problem with floating-point valued weights. Our overarching algorithm uses an iteratively reweighted least squares framework. This generates a sequence of Laplacian linear systems, which we solve using parallel matrix algorithms. Our overall implementation is up to 30-times faster than a serial solver when using 128 cores.