Sign in
Back
StUSPACE(log n) ⊂-DSPACE(log2 n/log log n)
Book chapter

StUSPACE(log n) ⊂-DSPACE(log2 n/log log n)

Eric Allender and Klaus-Jörn Lange
Algorithms and Computation, pp.193-202
Lecture Notes in Computer Science, Springer Berlin Heidelberg
10/11/2005
DOI: https://doi.org/10.1007/BFb0009495

Abstract

We present a deterministic algorithm running in space O (log2n/log log n) solving the connectivity problem on strongly unambiguous graphs. In addition, we present an O(log n) time-bounded algorithm for this problem running on a parallel pointer machine.

Metrics

7 Record Views

Details