Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
RUSPACE(log
n
)
Í\subseteq DSPACE(log2
n
/log log
n
)
| |
|
RUSPACE(log n) DSPACE(log 2
n/log log n)
E. Allender1 and K.-J. Lange2
| (1) |
Department of Computer Science, Rutgers University, Piscataway, NJ 08855, USA allender@cs.rutgers.edu , US |
| (2) |
Wilhelm-Schickard Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany lange@informatik.uni-tuebingen.de, DE |
Abstract. We present a deterministic algorithm running in space O(log 2
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.
Received February 1997, and in revised form August 1997, and in final form February 1998.
Fulltext Preview (Small, Large)
|
|
|
|
|
|