Publication Details
Title: On Removing Randomness from a Parallel Algorithm for Minimum Cuts
Author: M. Luby, J. Naor, and M. Naor
Group: ICSI Technical Reports
Date: February 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-007.pdf
Overview:
The weighted minimum cut problem in a graph is a fundamental problem in combinatorial optimization. Recently, Karger suggested a randomized parallel algorithm for this problem. We show that a similar algorithm can be implemented using only O(log^2 n) random bits. We also show that our result holds for computing minimum weight k-cuts, where k is fixed.
Bibliographic Information:
ICSI Technical Report TR-93-007
Bibliographic Reference:
M. Luby, J. Naor, and M. Naor. On Removing Randomness from a Parallel Algorithm for Minimum Cuts. ICSI Technical Report TR-93-007, February 1993
Author: M. Luby, J. Naor, and M. Naor
Group: ICSI Technical Reports
Date: February 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-007.pdf
Overview:
The weighted minimum cut problem in a graph is a fundamental problem in combinatorial optimization. Recently, Karger suggested a randomized parallel algorithm for this problem. We show that a similar algorithm can be implemented using only O(log^2 n) random bits. We also show that our result holds for computing minimum weight k-cuts, where k is fixed.
Bibliographic Information:
ICSI Technical Report TR-93-007
Bibliographic Reference:
M. Luby, J. Naor, and M. Naor. On Removing Randomness from a Parallel Algorithm for Minimum Cuts. ICSI Technical Report TR-93-007, February 1993