DIMACS TR: 97-50
RUSPACE(log n) is contained in DSPACE(log^2 n / loglog n)
Authors: Eric Allender and Klaus-Joern Lange
ABSTRACT
We present a deterministic algorithm running in space
O(log^2 n/ loglog 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.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-50.ps.gz
DIMACS Home Page