Traversing graphs in small space
We sketch two algorithms that solve the undirected st-connectivity problem in a small amount of space. One is due to Nisan, Szemeredy and Wigderson, and takes space O(log(3)/(2) n), where n denotes the number of nodes in a give undirected graph. This is the first algorithm that overcame the Savitch barrier on the space complexity of the problem. The other is due to Tarui and this author, and takes space O(sw(G)(2) log(2) n), where sw(G) denotes the separation-width of a given graph G. Their result implies that the st-connectivity problem can be solved in logarithmic space for any class of graphs with separation-width bounded above by a predetermined constant. This: class is one of few nontrivial classes for which the st-connectivity problem can be solved in logarithmic space.
st-connectivity problem logarithmic space graph algorithm randomization computational complexity theory