All reports by Author Derrick Stolee:

__
TR11-060
| 15th April 2011
__

Brady Garvin, Derrick Stolee, Raghunath Tewari, Vinodchandran Variyam#### ReachFewL = ReachUL

__
TR10-154
| 8th October 2010
__

Derrick Stolee, Vinodchandran Variyam#### Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs

__
TR09-049
| 5th May 2009
__

Derrick Stolee, Chris Bourke, Vinodchandran Variyam#### A log-space algorithm for reachability in planar DAGs with few sources

Brady Garvin, Derrick Stolee, Raghunath Tewari, Vinodchandran Variyam

We show that two complexity classes introduced about two decades ago are equal. ReachUL is the class of problems decided by nondeterministic log-space machines which on every input have at most one computation path from the start configuration to any other configuration. ReachFewL, a natural generalization of ReachUL, is the ... more >>>

Derrick Stolee, Vinodchandran Variyam

We consider the reachability problem for a certain class of directed acyclic graphs embedded on surfaces. Let ${\cal G}(m,g)$ be the class of directed acyclic graphs with $m = m(n)$ source vertices embedded on a surface (orientable or non-orientable) of genus $g = g(n)$. We give a log-space reduction that ... more >>>

Derrick Stolee, Chris Bourke, Vinodchandran Variyam

Designing algorithms that use logarithmic space for graph reachability problems is fundamental to complexity theory. It is well known that for general directed graphs this problem is equivalent to the NL vs L problem. For planar graphs, the question is not settled. Showing that the planar reachability problem is NL-complete ... more >>>