Skip to Main Content
 

Global Search Box

 
 
 
 

ETD Abstract Container

Abstract Header

Deciding st-connectivity in undirected graphs using logarithmic space

Maceli, Peter Lawson

Abstract Details

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

Citations

  • Maceli, P. L. (2008). Deciding st-connectivity in undirected graphs using logarithmic space [Master's thesis, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1211753530

    APA Style (7th edition)

  • Maceli, Peter. Deciding st-connectivity in undirected graphs using logarithmic space. 2008. Ohio State University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1211753530.

    MLA Style (8th edition)

  • Maceli, Peter. "Deciding st-connectivity in undirected graphs using logarithmic space." Master's thesis, Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=osu1211753530

    Chicago Manual of Style (17th edition)