minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms
There are several fundamental problems for which there are optimal randomized algorithms, but whose deterministic complexity remains unresolved. Among such problems are the minimum spanning tree problem, the set maxima problem, the problem of computing connected components and (minimum) spanning trees in parallel and the problem of performing sensitivity analysis on shortest path trees and minimum spanning trees. For each of these problems there is an optimal randomized algorithm which uses a linear number of random bits. We propose new algorithms (or adapt old ones) for these problems which preserve optimality while saving an exponential number of random bits. In the case of computing minimum spanning trees and MST/SSSP sensitivity analysis, we reduce the dependence on randomness to log* n random bits.We also consider the problem of selection, for which we give two algorithms which make an expected 1.5n + o(n) comparisons; one uses O (log n ) random bits and is uniform, the other uses O (log log n ) random bits and is non-uniform.
randomization minimum spanning tree trees parallel connection algorithm optimality randomized algorithm complexity computation component sensitivity analysis shortest path case dependencies log select