On Removing Randomness from a Parallel Algorithm for Minimum Cuts
Title | On Removing Randomness from a Parallel Algorithm for Minimum Cuts |
Publication Type | Technical Report |
Year of Publication | 1993 |
Authors | Luby, M., Naor J., & Naor M. |
Other Numbers | 795 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1993/tr-93-007.pdf |
Bibliographic Notes | ICSI Technical Report TR-93-007 |
Abbreviated Authors | M. Luby, J. Naor, and M. Naor |
ICSI Publication Type | Technical Report |