A SPECTRUM OF TIME-SPACE TRADE-OFFS FOR UNDIRECTED S-T CONNECTIVITY

We present a family of randomized algorithms that enjoys a wide range of time-space trade-offs in deciding undirected S-T-connectivity. Our trade-offs cover the whole range between breadth first search and the random walk procedure of Aleliunas at al., and achieve a time-space pr oduct of (O) over tilde(mn) (where n is the number of vertices in the graph, m is the number of edges, and (O) over tilde notation is used i n order to suppress logarithmic terms). Moreover, we obtain improved t ime-space trade-offs of (O) over tilde(n(2)) for regular graphs. A con venient and informative way of expressing our trade-offs, that implies the trade-offs stated above, is as (O) over tilde((Sigma(i=1)(n) d(i) )(Sigma(i=1)(n) 1/d(i))), where d(i) is the degree of vertex i in the input graph. In constructing our algorithms and analysing them, we bui ld upon earlier work of Broder et al. (who achieved a time-space trade -off of (O) over tilde(m(2))), Barnes and Feige (who achieved a time-s pace trade-off of (O) over tilde(m(3/2)n(1/2))), and Aldous. In passin g, we also improve previous results regarding the rate at which a rand om walk discovers new vertices in a graph. (C) 1997 Academic Press.