An O(log(n)4/3) space algorithm for (s, t) connectivity in undirected graphs

ABSTRACT

We present a deterministic algorithm that computes st-connectivity in undirected graphs using O(log 4/3n) space. This improves the previous O(log3/2n) bound of Nisan et al. [1992].

REFERENCES

• 1: ALELIUNAS, R., KARP, R. M., LIPTON, R. J., LOV~.SZ, L., AND RACKOFF, C. 1979. Random walks, universal traversal sequences, and the complexity of maze problems. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science (San Juan, Puerto Rico, Oct. 29-31). IEEE, Computer Society Press, Los Alamitos, Calif., pp. 218-223.
• 2: Greg Barnes , Uriel Feige, Short Random Walks on Graphs, SIAM Journal on Discrete Mathematics, v.9 n.1, p.19-28, Feb. 1996 [doi>10.1137/S0895480194264988]
• 3: Mihir Bellare , Oded Goldreich , Shafi Goldwasser, Randomness in interactive proofs, Computational Complexity, v.3 n.4, p.319-354, Oct. 1993 [doi>10.1007/BF01275487]
• 4: BELLARE, M. AND ROMPEL, J. 1994. Randomness-efficient oblivious sampling. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (Los Alamitos, Calif., Nov. 1994), S. Goldwasser, Ed., IEEE Computer Society Press, Los Alamitos, Calif., pp. 276-287.
• 5: LEWIS, H. R. AND PAPADIMITRIOU, C.H. 1982. Symmetric space-bounded computation. Theoret. Comput. Sci. 19, 2 (Aug.), 161-187.
• 6: NISAN, N. 1992. Pseudorandom generators for space-bounded computation. Combinatorica 12, 4, 449-461.
• 7: Noam Nisan, RL⊆SC , Computational Complexity, v.4 n.1, p.1-11, Jan. 1994 [doi>10.1007/BF01205052]
• 8: NISAN, N., SZEMEREDI, E., AND WIGDERSON, A. 1992. Undirected connectivity in O(logl5n) space. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (Pittsburgh, Pa. Oct.). IEEE Computer Society Press, Los Alamitos, Calif., pp. 24-29.
• 9: SAKS AND ZHOU, S. 1999. BPIISPACE(S) C_ DSPACE(S3/2). J. Comput. Syst. Sci. 58.
• 10: SAVITCH, W.J. 1970. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4, 2 (Apr.), 177-192.
• 11: David Zuckerman, Randomness-optimal sampling, extractors, and constructive leader election, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.286-295, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237878]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing

General Terms:
Algorithms, Theory

Keywords:
computational complexity, derandomization, short pseudorandom walks on graphs, space bounded computations, undirected graph connectivity