RUSPACE(LOG N) SUBSET-OF DSPACE(LOG(2)-N-LOG-LOG-N)

Authors
ALLENDER E LANGE KJ
Citation
E. Allender et Kj. Lange, RUSPACE(LOG N) SUBSET-OF DSPACE(LOG(2)-N-LOG-LOG-N), theory of computing systems, 31(5), 1998, pp. 539-550
Citations number
26
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
theory of computing systems → ACNP
Volume
31
Issue
5
Year of publication
1998
Pages
539 - 550
Database
ISI
SICI code
Abstract
We present a deterministic algorithm running in space O(log(2) n/log l og 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.