Search ETDs:
Deciding st-connectivity in undirected graphs using logarithmic space
Maceli, Peter Lawson

2008, Master of Science, Ohio State University, Mathematics.

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.


Neil Robertson (Advisor)
Tim Carlson (Committee Member)

Recommended Citations

Hide/Show APA Citation

Maceli, P. (2008). Deciding st-connectivity in undirected graphs using logarithmic space. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Maceli, Peter. "Deciding st-connectivity in undirected graphs using logarithmic space." Electronic Thesis or Dissertation. Ohio State University, 2008. OhioLINK Electronic Theses and Dissertations Center. 25 Sep 2017.

Hide/Show Chicago Citation

Maceli, Peter "Deciding st-connectivity in undirected graphs using logarithmic space." Electronic Thesis or Dissertation. Ohio State University, 2008. https://etd.ohiolink.edu/

Files

osu1211753530.pdf (237.07 KB) View|Download