
For FullText 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
Seinosuke TODA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E83D
No.3
pp.392396 Publication Date: 2000/03/25 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: INVITED SURVEY PAPER Category: Graph Algorithms Keyword: stconnectivity problem, logarithmic space, graph algorithm, randomization, computational complexity theory,
Full Text: PDF>>
Summary:
We sketch two algorithms that solve the undirected stconnectivity 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 separationwidth of a given graph G. Their result implies that the stconnectivity problem can be solved in logarithmic space for any class of graphs with separationwidth bounded above by a predetermined constant. This class is one of few nontrivial classes for which the stconnectivity problem can be solved in logarithmic space.

