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 |