Document Open Access Logo

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

Authors Ryo Ashida, Kotaro Nakagawa

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.5.pdf
  • Filesize: 0.63 MB
  • 13 pages

Document Identifiers

Author Details

Ryo Ashida
Kotaro Nakagawa

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.SoCG.2018.5

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.

Subject Classification

Keywords
  • graph reachability
  • grid graph
  • graph algorithm
  • sublinear space algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Eric Allender, David A Mix Barrington, Tanmoy Chakraborty, Samir Datta, and Sambuddha Roy. Planar and grid graph reachability problems. Theory of Computing Systems, 45(4):675-723, 2009. Google Scholar
  2. Tetsuo Asano and Benjamin Doerr. Memory-constrained algorithms for shortest path problem. In CCCG, 2011. Google Scholar
  3. Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, and Osamu Watanabe. Õ(√n)-space and polynomial-time algorithm for planar directed graph reachability. In International Symposium on Mathematical Foundations of Computer Science, pages 45-56. Springer, 2014. Google Scholar
  4. Greg Barnes, Jonathan F Buss, Walter L Ruzzo, and Baruch Schieber. A sublinear space, polynomial time algorithm for directed st connectivity. SIAM Journal on Computing, 27(5):1273-1282, 1998. Google Scholar
  5. Chris Bourke, Raghunath Tewari, and NV Vinodchandran. Directed planar reachability is in unambiguous log-space. ACM Transactions on Computation Theory (TOCT), 1(1):4, 2009. Google Scholar
  6. Gerard Jennhwa Chang. Algorithmic aspects of domination in graphs. Handbook of Combinatorial Optimization, pages 221-282, 2013. Google Scholar
  7. Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, NV Vinodchandran, and Osamu Watanabe. An O(n^1/2+ε)-space and polynomial-time algorithm for directed planar reachability. In Computational Complexity (CCC), 2013 IEEE Conference on, pages 277-286. IEEE, 2013. Google Scholar
  8. Omer Reingold. Undirected connectivity in log-space. Journal of the ACM (JACM), 55(4):17, 2008. Google Scholar
  9. Derrick Stolee and NV Vinodchandran. Space-efficient algorithms for reachability in surface-embedded graphs. In Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on, pages 326-333. IEEE, 2012. Google Scholar
  10. Leslie G Valiant. Universality considerations in vlsi circuits. IEEE Transactions on Computers, 100(2):135-140, 1981. Google Scholar
  11. Avi Wigderson. The complexity of graph connectivity. Mathematical Foundations of Computer Science 1992, pages 112-132, 1992. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact