An O (log( n ) 4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
Authors:
Open Access
- 1 March 2000
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 47 (2) , 294-311
Abstract
We present a deterministic algorithm that computes st -connectivity in undirected graphs using O (log 4/3 n ) space. This improves the previous O (log 3/2 n ) bound of Nisan et al. [1992].Keywords
This publication has 10 references indexed in Scilit:
- Randomness-efficient oblivious sampling2002
- Short Random Walks on GraphsSIAM Journal on Discrete Mathematics, 1996
- Randomness-optimal sampling, extractors, and constructive leader election1996
- RL $ \subseteq $ SCcomputational complexity, 1994
- Randomness in interactive proofscomputational complexity, 1993
- Pseudorandom generators for space-bounded computationCombinatorica, 1992
- Undirected connectivity in O(log/sup 1.5/n) space1992
- Symmetric space-bounded computationTheoretical Computer Science, 1982
- Random walks, universal traversal sequences, and the complexity of maze problems1979
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970