2026-07-21T14:10:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8718 2024-03-06T10:42:29Z ddc:004 open_access

O~(n^{1/3})-Space Algorithm for the Grid Graph Reachability Problem Ashida, Ryo Nakagawa, Kotaro graph reachability grid graph graph algorithm sublinear space algorithm The directed graph reachability problem takes as input an n-vertex directed graph G=(V,E), and two distinguished vertices s and t. The problem is to determine whether there exists a path from s to t in G. This is a canonical complete problem for class NL. Asano et al. proposed an O~(sqrt{n}) space and polynomial time algorithm for the directed grid and planar graph reachability problem. The main result of this paper is to show that the directed graph reachability problem restricted to grid graphs can be solved in polynomial time using only O~(n^{1/3}) space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ryo Ashida and Kotaro Nakagawa 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.5 urn:nbn:de:0030-drops-87182 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.5 eng https://creativecommons.org/licenses/by/3.0/legalcode