We survey a number of algorithms that decide connectivity in undirected graphs. Our focus is on the use of random walks as a tool in reducing the space complexity of these algorithms.

Back to Discrete Probability and Algorithms Table of Contents

Back to the IMA Home Page