All reports by Author David Kirkpatrick:

__
TR14-071
| 7th May 2014
__

Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe#### O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem

Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe

We show an O(sqrt(n))-space and polynomial-time algorithm for solving the planar directed graph reachability problem. Imai et al. showed in CCC 2013 that the problem is solvable in O(n^{1/2+eps})-space and polynomial-time by using separators for planar graphs, and it has been open whether the space bound can be improved to ... more >>>