Traversing Graphs in Small Space

Seinosuke TODA  

IEICE TRANSACTIONS on Information and Systems   Vol.E83-D   No.3   pp.392-396
Publication Date: 2000/03/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Graph Algorithms
st-connectivity problem,  logarithmic space,  graph algorithm,  randomization,  computational complexity theory,  

Full Text: PDF>>
Buy this Article

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(log3/2n), 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 log2 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.