Deciding st-connectivity in undirected graphs using logarithmic space
In 2004 Omer Reingold gave a deterministic log-space algorithm which solves the problem of st-connectivity in undirected graphs. The motivating idea behind Reingold's algorithm was the observation that this problem is essentially trivial for constant degree graphs with logarithmic diameter. The crux of Reingold's algorithm is that an arbitrary undirected graph can be transformed in log-space into such a graph. Though this transformation results in a much more complicated graph it allows us to solve this fundamental algorithmic question in log-space.
Additionally, the problem of undirected st-connectivity is complete for the space complexity class SL, the class of problems solvable by symmetric, non-deterministic, log-space computations. And so as a corollary to Reingold's log-space algorithm we have that SL=L, where L is the class of problems solvable by deterministic log-space computations.
In this thesis, we examine this algorithm in depth and discuss a number of its consequences.
School:The Ohio State University
School Location:USA - Ohio
Source Type:Master's Thesis
Keywords:ustcon log space expander graphs graph connectivity
Date of Publication:01/01/2008