Startseite > Publikationen > Publikationen


Martinez, Gabriel Terán;Meyer auf der Heide, Friedhelm:

Communication-efficient parallel multiway- and approximate minimum-cut computation.

Proc. of LATIN 1998 : S. 316-330, Jun. 1998


Abstract. We examine different variants of minimum cut problems on undirected weighted graphs on the p-processor bulk synchronous parallel (BSP) model of Valiant. This model and the corresponding cost measure guide algorithm designers to develop work efficient algorithms that need only very little communication. Karger and Stein have presented a recursive contraction algorithm to solve minimum cut problems. They suggest a PRAM implementation of their algorithm working in polynomial polylogarithmic time, but being not work-optimal. Typically the problem size n is much larger than the number of processors p on real-world parallel computers (p << n). For this setting we present improved BSP implementations of the algorithm of Karger and Stein. For the case of multiway cut and approximate minimum cut we obtain optimal, communication efficient results. A nice effect, beside the optimality, is that communication is efficient for a large spectrum of BSP-parameters. In the case of the minimal cut problem our results are close to optimal.




author = {Martinez, Gabriel Terán and Meyer auf der Heide, Friedhelm},
title = {Communication-efficient parallel multiway- and approximate minimum-cut computation},
journal = {Proc. of LATIN 1998},
pages = {316-330},
month = jun,
year = {1998},

BibTeX in die Zwischenablage kopieren