Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > DAVID KIRKPATRICK:
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

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




ISSN 1433-8092 | Imprint