Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SIMULTANEOUS TIME SPACE BOUND:
Reports tagged with simultaneous time space bound:
TR15-016 | 16th January 2015
Diptarka Chakraborty, Raghunath Tewari

#### An $O(n^{\epsilon})$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

Revisions: 1

Given a graph $G$ and two vertices $s$ and $t$ in it, {\em graph reachability} is the problem of checking whether there exists a path from $s$ to $t$ in $G$. We show that reachability in directed layered planar graphs can be decided in polynomial time and $O(n^\epsilon)$ space, for ... more >>>

ISSN 1433-8092 | Imprint