Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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