%0 Journal Article %1 reingold08 %A Reingold, Omer %C New York, NY, USA %D 2008 %I ACM %J J. ACM %K complexity expander ustcon %N 4 %P 17:1--17:24 %R 10.1145/1391289.1391291 %T Undirected Connectivity in Log-space %V 55 %X 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 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.

@article{reingold08, 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 log4/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.}, acmid = {1391291}, added-at = {2015-04-06T13:03:17.000+0200}, address = {New York, NY, USA}, articleno = {17}, author = {Reingold, Omer}, biburl = {https://www.bibsonomy.org/bibtex/223315019a2ebbf15a98a1bba479bd188/ytyoun}, doi = {10.1145/1391289.1391291}, interhash = {d3e2b3350f157e3196f014beff3138d3}, intrahash = {23315019a2ebbf15a98a1bba479bd188}, issn = {0004-5411}, issue_date = {September 2008}, journal = {J. ACM}, keywords = {complexity expander ustcon}, month = sep, number = 4, numpages = {24}, pages = {17:1--17:24}, publisher = {ACM}, timestamp = {2016-11-01T10:03:03.000+0100}, title = {Undirected Connectivity in Log-space}, volume = 55, year = 2008 }