-
- Omer Reingold
- Weizmann Institute of Science Rehovot, Rehovot, Israel
この論文をさがす
説明
<jats:p> We present a <jats:italic>deterministic</jats:italic> , log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log <jats:sup>4/3</jats:sup> (⋅) 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 <jats:italic>O</jats:italic> (log <jats:italic>n</jats:italic> log log <jats:italic>n</jats:italic> )-space, deterministic algorithm for undirected st-connectivity. </jats:p> <jats:p> Our algorithm also implies a way to construct in log-space a <jats:italic>fixed</jats:italic> 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. </jats:p>
収録刊行物
-
- Journal of the ACM
-
Journal of the ACM 55 (4), 1-24, 2008-09
Association for Computing Machinery (ACM)
