Abstract.
We present a deterministic algorithm running in space O(log2 n /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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received February 1997, and in revised form August 1997, and in final form February 1998.
Rights and permissions
About this article
Cite this article
Allender, E., Lange, KJ. RUSPACE(log n) \(\subseteq\) DSPACE(log2 n/log log n) . Theory Comput. Systems 31, 539–550 (1998). https://doi.org/10.1007/s002240000102
Issue Date:
DOI: https://doi.org/10.1007/s002240000102