DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2018.5

O~(n^{1/3})-Space Algorithm for the Grid Graph Reachability Problem

Authors: Ryo Ashida and Kotaro Nakagawa

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract

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.

Cite as

Ryo Ashida and Kotaro Nakagawa. O~(n^{1/3})-Space Algorithm for the Grid Graph Reachability Problem. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ashida_et_al:LIPIcs.SoCG.2018.5,
  author =	{Ashida, Ryo and Nakagawa, Kotaro},
  title =	{{O\textasciitilde(n^\{1/3\})-Space Algorithm for the Grid Graph Reachability Problem}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.5},
  URN =		{urn:nbn:de:0030-drops-87182},
  doi =		{10.4230/LIPIcs.SoCG.2018.5},
  annote =	{Keywords: graph reachability, grid graph, graph algorithm, sublinear space algorithm}
}

Search Results

Documents authored by Nakagawa, Kotaro

O~(n^{1/3})-Space Algorithm for the Grid Graph Reachability Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message