REPORTS > DETAIL:
Paper:
TR96-048 | 12th September 1996 00:00
StUSPACE(log n) is Contained in DSPACE((log^2 n)/loglog n)
TR96-048 Authors: Eric Allender, Klaus-Jörn Lange
Publication: 13th September 1996 19:47
Downloads: 185
Keywords:
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.