Title :
An O(n½+?)-Space and Polynomial-Time Algorithm for Directed Planar Reachability
Author :
Imai, Tetsuro ; Nakagawa, Koichi ; Pavan, A. ; Vinodchandran, N.V. ; Watanabe, Osamu
Author_Institution :
Dept. of Math. & Comput. Sci., Tokyo Inst. of Technol., Tokyo, Japan
Abstract :
We show that the reachability problem over directed planar graphs can be solved simultaneously in polynomial time and approximately O(√n) space. In contrast, the best space bound known for the reachability problem on general directed graphs with polynomial running time is O(n/2√log n).
Keywords :
computational complexity; directed graphs; reachability analysis; directed planar graphs; directed planar reachability; general directed graphs; polynomial-time algorithm; space algorithm; Algorithm design and analysis; Complexity theory; Face; Particle separators; Polynomials; Silicon; Standards; directed planar graph; polynomial time; reachability; sublinear space;
Conference_Titel :
Computational Complexity (CCC), 2013 IEEE Conference on
Conference_Location :
Stanford, CA
DOI :
10.1109/CCC.2013.35
