For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Traversing Graphs in Small Space
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/03/25
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>>
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.