An $O(\logn \log\logn)$ Space Algorithm for Undirected st-Connectivity
Vladimir Trifonov · SIAM Journal on Computing · 2005
We present a deterministic $O(\log n \log \log n)$ space algorithm for undirected st-connectivity. It is based on a space-efficient simulation of the deterministic EREW algorithm of Chong and Lam [J. Algorithms, 18 (1995), pp. 378–402], an approach suggested by Prof. Vijaya Ramachandran, and uses the universal exploration sequences for trees constructed by Koucký in [Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001, pp. 21–27]. Our result improves the $O(\log^{4/3} n)$ bound of Armoni et al. in [Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1997, pp. 230–239] 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 in [Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 376–385].