Undirected connectivity in log-space

Author:
Top Cited Papers
Open Access
Publisher website
Google Scholar
Abstract
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.
Funding Information
  • United States-Israel Binational Science Foundation (2.00E+13)

This publication has 43 references indexed in Scilit: