Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TIME-SPACE BOUNDS:
Reports tagged with time-space bounds:
TR10-154 | 8th October 2010
Derrick Stolee, N. V. Vinodchandran

#### Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs

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 >>>

ISSN 1433-8092 | Imprint