ABSTRACT

Although the first significant application of randomized techniques in algorithm design happened in mid-1970s in the celebrated primality testing algorithms of Miller-Rabin and Solovay-Strassen, its impact in graph algorithms was felt more than a decade later. Arguably, the first non-trivial applications were in the area of parallel graph algorithms like connectivity [1], depth-first search (DFS) [2], and matching [3]. Luby’s work [4] on parallel maximal matching inspired a new line of work in derandomization. Seidel’s work [5] in shortest paths was soon followed by some very innovative approaches to global min-cuts and minimum spanning trees (MSTs) by Karger et al. [6,7] that consolidated the use of randomization in the area of mainstream graph algorithms. Subsequently, randomization has been used very effectively in dynamic graph algorithms such as connectivity [8], transitive closure, and shortest path maintenance problems, some of which have no matching deterministic counterparts.