Journal of the ACM · 2008 · 511 citations · 41 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationComputational ComplexityGraph AlgorithmsGraph TheoryRandomized ComplexitySpace ComplexityAlgorithmic Graph TheoryComputational Complexity Of Graph AlgorithmsConnectivity AlgorithmsGraph Traversal AlgorithmsLabelingLogarithmic SpaceLogarithmic Space ComplexitySpace Complexity Of Graph Problems
Previous work bounded undirected st‑connectivity space complexity at log 4/3, and Trifonov later achieved an O(log n log log n) deterministic log‑space algorithm. We present a deterministic log‑space algorithm that solves undirected st‑connectivity. The algorithm deterministically computes st‑connectivity within logarithmic space. This algorithm establishes SL = L and yields log‑space constructible universal traversal and exploration sequences for connected graphs.
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 log 4/3 (⋅) obtained by Armoni, Ta-Shma, Wigderson and Zhou (JACM 2000). As undirected st-connectivity is complete for the class of problems solvable by symmetric, nondeterministic, log-space computations (the class SL), this algorithm implies that SL = L (where L is the class of problems solvable by deterministic log-space computations). Independent of our work (and using different techniques), Trifonov (STOC 2005) has presented an O (log n log log n )-space, deterministic algorithm for undirected st-connectivity. Our algorithm also implies a way to construct in log-space a fixed sequence of directions that guides a deterministic walk through all of the vertices of any connected graph. Specifically, we give log-space constructible universal-traversal sequences for graphs with restricted labeling and log-space constructible universal-exploration sequences for general graphs.
41
COMBINATORICA · 1986 · 1.2K citations
Alexander Lubotzky, Ralph S. Phillips, Peter Sarnak · COMBINATORICA · 1988 · 1K citations
Random walks, universal traversal sequences, and the complexity of maze problems
Romas Aleliunas, Richard M. Karp, Richard J. Lipton et al. · 1979 · 705 citations