All reports by Author Lin Yang:

__
TR14-035
| 13th March 2014
__

Diptarka Chakraborty, A. Pavan, Raghunath Tewari, Vinodchandran Variyam, Lin Yang#### New Time-Space Upperbounds for Directed Reachability in High-genus and $H$-minor-free Graphs.

Diptarka Chakraborty, A. Pavan, Raghunath Tewari, Vinodchandran Variyam, Lin Yang

We obtain the following new simultaneous time-space upper bounds for the directed reachability problem.

(1) A polynomial-time,

$\tilde{O}(n^{2/3}g^{1/3})$-space algorithm for directed graphs embedded on orientable surfaces of genus $g$. (2) A polynomial-time, $\tilde{O}(n^{2/3})$-space algorithm for all $H$-minor-free graphs given the tree decomposition, and (3) for $K_{3, 3}$-free and ...
more >>>