arXiv Open Access 2015

A Parallel Min-Cut Algorithm using Iteratively Reweighted Least Squares

Yao Zhu David F. Gleich

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DC cs.DS math.NA

Penulis (2)

Yao Zhu

David F. Gleich

Format Sitasi

APA MLA BibTeX

Zhu, Y., Gleich, D.F. (2015). A Parallel Min-Cut Algorithm using Iteratively Reweighted Least Squares. https://arxiv.org/abs/1501.03105

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2015
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓