Abstract
The directed graph reachability problem takes as input an n-vertex directed graph Gā=ā(V,E), and two distinguished vertices v 0, and vertex v *. The problem is to determine whether there exists a path from v 0 to v * in G. The main result of this paper is to show that the directed graph reachability problem restricted to planar graphs can be solved in polynomial time using only \(\widetilde{O}(\sqrt{n})\) space.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Allender, E., Mahajan, M.: The complexity of planarity testing. Information and ComputationĀ 189(1), 117ā134 (2004)
Asano, T., Doerr, B.: Memory-constrained algorithms for shortest path problem. In: Proc. of the 23th Canadian Conf. on Comp. Geometry, CCCG 1993 (2011)
Asano, T., Kirkpatrick, D.: A \(O(\sqrt{n})\)-space algorithm for reporting a shortest path on a grid graph (in preparation)
Barnes, G., Buss, J.F., Ruzzo, W.L., Schieber, B.: A sublinear space, polynomial time algorithm for directed s-t connectivity. In: Proc. Structure in Complexity Theory Conference, pp. 27ā33. IEEE (1992)
Edmonds, J., Poon, C.K., Achlioptas, D.: Tight lower bounds for st-connectivity on the NNJAG model. SIAM J. Comput.Ā 28(6), 2257ā2284 (1999)
Gazit, H., Miller, G.L.: A parallel algorithm for finding a separator in planer graphs. In: Proc. of the 28th Ann. Sympos. on Foundations of Comp. Sci. (FOCS 1987), pp. 238ā248 (1987)
Henzinger, M.R., Klein, P., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. Journal of Comput. Syst. Sci.Ā 55, 3ā23 (1997)
Imai, T., Nakagawa, K., Pavan, A., Vinodchandran, N.V., Watanabe, O.: An \(O({n^{{1\over 2}+\epsilon}})\)-space and polynomial-time algorithm for directed planar reachability. In: Proc. of the 28th Conf. on Comput. Complexity, pp. 277ā286 (2013)
Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. J. Comput. Syst. Sci.Ā 32(3), 265ā279 (1986)
Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM Journal on Applied MathematicsĀ 36(2), 177ā189 (1979)
Pippenger, N., Fischer, M.J.: Relations among complexity measures. J. ACMĀ 26(2), 361ā381 (1979)
Reingold, O.: Undirected connectivity in log-space. J. ACMĀ 55(4) (2008)
Wigderson, A.: The complexity of graph connectivity. In: Havel, I.M., Koubek, V. (eds.) MFCS 1992. LNCS, vol.Ā 629, pp. 112ā132. Springer, Heidelberg (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
Ā© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Asano, T., Kirkpatrick, D., Nakagawa, K., Watanabe, O. (2014). \(\widetilde{O}(\sqrt{n})\)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability. In: Csuhaj-VarjĆŗ, E., Dietzfelbinger, M., Ćsik, Z. (eds) Mathematical Foundations of Computer Science 2014. MFCS 2014. Lecture Notes in Computer Science, vol 8635. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44465-8_5
Download citation
DOI: https://doi.org/10.1007/978-3-662-44465-8_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44464-1
Online ISBN: 978-3-662-44465-8
eBook Packages: Computer ScienceComputer Science (R0)