RUSPACE(log n) $\subseteq$ DSPACE(log2 n/log log n)

E Allender; K.-J Lange

doi:10.1007/s002240000102

Back

$RUSPACE(log n) $\subseteq$ DSPACE(log2 n/log log n)$

Journal article

Peer reviewed

RUSPACE(log n) $\subseteq$ DSPACE(log2 n/log log n)

E Allender and K.-J Lange

Theory of Computing Systems, Vol.31(5), pp.539-550

09/10/1998

DOI: https://doi.org/10.1007/s002240000102

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.

Metrics

14 Record Views

11 Times Cited - Web of Science

Details

Title: RUSPACE(log n) $\subseteq$ DSPACE(log2 n/log log n)
Creators: E Allender - Department of Computer Science, Rutgers University, Piscataway, NJ 08855, USA allender@cs.rutgers.edu US
K.-J Lange - Wilhelm-Schickard Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany lange@informatik.uni-tuebingen.de DE
Publication Details: Theory of Computing Systems, Vol.31(5), pp.539-550
Date published: 09/10/1998
Publisher: Springer-Verlag
Academic Unit: Computer Science (SAS)
Language: English
Resource Type: Journal article
Identifiers: 991031653894604646