an o(log n log log n) space algorithm for undirected st-connectivity
We present a deterministic O(log n log log n) space algorithm for undirected st-connectivity. It is based on the deterministic EREW algorithm of Chong and Lam [6] and uses the universal exploration sequences for trees constructed by Kouck [13]. Our result improves the O(log 4/3 n) bound of Armoni et al.\ [2] and is a big step towards the optimal O(log n). Independently of our result and using a different set of techniques, the optimal bound was achieved by Reingold [18].
log space algorithm undirected st-connectivity exploration sequence trees optimality connection space complexity space-bounded computation