Deciding st-connectivity in undirected graphs using logarithmic space

by Maceli, Peter Lawson

Abstract (Summary)
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.
Bibliographical Information:


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

© 2009 All Rights Reserved.