A Parallel Min-Cut Algorithm using Iteratively Reweighted Least Squares
arXiv:1501.031054 citationsh-index: 39
Originality Incremental advance
AI Analysis
This work addresses the need for faster min-cut computation for large graphs, offering a practical parallel solution for practitioners.
The paper presents a parallel algorithm for the undirected s,t-mincut problem using iteratively reweighted least squares, achieving up to 30x speedup on 128 cores compared to a serial solver.
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.