Vladimir Trifonov
ABSTRACT
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(log4/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].
- R. Aleliunas, R. Karp, R. Lipton, L. Lovász, and C. Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In 20th IEEE Symposium on Foundations of Computer Science, pages 218--223, 1979.Google Scholar
Digital Library
- R. Armoni, A. Ta-Shma, A. Wigderson, and S. Zhou. SL ⊆ L4/3. In 20th ACM Symposium on Theory of Computing, pages 230--239, 1997. Google ScholarDigital Library
- B. Awerbuch and Y. Shiloach. New connectivity and MSF algorithms for ultracomputer and PRAM. In International Conference on Parallel Processing, pages 175--179, 1983.Google Scholar
- F. Chin, J. Lam, and I.-N. Chen. Efficient parallel algorithms for some graph problems. Communications of the ACM, 25:659--666, 1982. Google ScholarDigital Library
- K. Chong, Y. Han, and T. Lam. On the parallel time complexity of undirected connectivity and minimum spanning trees. Journal of the ACM, 48(2):297--323, 2001. Google ScholarDigital Library
- K. Chong and T. Lam. Finding connected components in O(log n log log n) time on the EREW PRAM. Journal of Algorithms, 18(3):378--402, 1995. Google ScholarDigital Library
- R. Cole and U. Vishkin. Approximate and exact parallel scheduling with applications to list, tree, and graph problems. In 27th IEEE Symposium on Foundations of Computer Science, pages 478--491, 1986.Google ScholarDigital Library
- H. Gazit. An optimal randomized parallel algorithm for finding connected components in a graph. In 27th IEEE Symposium on Foundations of Computer Science, pages 492--501, 1986.Google ScholarDigital Library
- S. Halperin and U. Zwick. Optimal randomized EREW PRAM algorithms for finding spanning forests and for other basic graph connectivity problems. In 7th ACM-SIAM Symposium on Discrete Algorithms, pages 438--447, 1996. Google ScholarDigital Library
- D. Hirschberg, A. Chandra, and D. Sarwate. Computing connected components on parallel computers. Communications of the ACM, 22(8):461--464, 1979. Google ScholarDigital Library
- D. Johnson and P. Metaxas. Connected components in O(log 3/2 |V|) parallel time for the CREW PRAM. In 32nd IEEE Symposium on Foundations of Computer Science, pages 688--697, 1991. Google ScholarDigital Library
- D. Karger, N. Nisan, and M. Parnas. Fast connected components algorithm for the EREW PRAM. In 4th ACM Symposium on Parallel Algorithms and Architectures, pages 373--381, 1992. Google ScholarDigital Library
- M. Koucký. Universal traversal sequences with backtracking. In 16th IEEE Conference on Computational Complexity, pages 21--27, 2001. Google ScholarDigital Library
- H. Lewis and C. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science, 19:161--187, 1982.Google ScholarCross Ref
- N. Nisan. Psuedorandom generators for space-bounded computation. In 22nd ACM Symposium on Theory of Computing, pages 204--212, 1990. Google ScholarDigital Library
- N. Nisan, E. Szemeredi, and A. Wigderson. Undirected connectivity in O(\log1.5 n) space. In 33rd IEEE Symposium on Foundations of Computer Science, pages 24--29, 1992.Google Scholar
- S. Pettie and V. Ramachandran. A randomized time-work optimal parallel algorithm for finding a minimum spanning forest. SIAM Journal on Computing, 31(6):1879--1895, 2002. Google ScholarDigital Library
- O. Reingold. Undirected st-connectivity in log-space. In these proceedings, 2005. Google ScholarDigital Library
- C. Savage and J. JáJá. Fast, efficient parallel algorithms for some graph problems. SIAM Journal on Computing, 10(4):682--691, 1981.Google ScholarCross Ref
- W. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177--192, 1970.Google ScholarDigital Library
- Y. Shiloach and U. Vishkin. An O(log n) parallel connectivity algorithm. Journal of Algorithms, 3(1):57--67, 1982. Google ScholarDigital Library
- R. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146--160, 1972.Google ScholarDigital Library
- R. Tarjan and U. Vishkin. An efficient parallel biconnectivity algorithm. SIAM Journal on Computing, 14(4):862--874, 1985.Google ScholarDigital Library
- V. Trifonov. An O(log n log log n) space algorithm for undirected st-connectivity. Technical Report TR04-114, Electronic Colloquium on Computational Complexity, http://www.eccc.uni-trier.de/eccc/, 2004.Google Scholar
Index Terms
- An O(log n log log n) space algorithm for undirected st-connectivity
Recommendations
Undirected connectivity in log-space
We present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log4/3(⋅) obtained by Armoni, Ta-Shma, Wigderson and Zhou (JACM 2000). As ...
An $O(\logn \log\logn)$ 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 a space-efficient simulation of the deterministic EREW algorithm of Chong and Lam [J. Algorithms, 18 (1995), pp. 378-402], an approach ...
Undirected ST-connectivity in log-space
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computingWe present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log4/3 obtained by Armoni, Ta-Shma, Wigderson and Zhou [9]. As undirected st-...
Comments