O(n^1/3)-space algorithm for the grid graph reachability problem

DOI10.4230/LIPICS.SOCG.2018.5zbMATH Open1489.68180arXiv1803.07097MaRDI QIDQ5115772FDOQ5115772

Authors: Ryo Ashida, Kotaro Nakagawa 

Publication date: 18 August 2020

Full work available at URL: https://arxiv.org/abs/1803.07097

Recommendations

• \(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability
• An $$O(n^{\epsilon })$$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
• An O ( n ^ϵ ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Planar and grid graph reachability problems

zbMATH Keywords

graph algorithmgrid graphgraph reachabilitysublinear space algorithm

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Cites Work

• Undirected connectivity in log-space
• Universality considerations in VLSI circuits
• Planar and grid graph reachability problems
• Directed planar reachability is in unambiguous log-space
• The complexity of graph connectivity
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• \(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability

Cited In (7)

• Planar and grid graph reachability problems
• \(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability
• Space complexity of the directed reachability problem over surface-embedded graphs
• Title not available (Why is that?)
• Space-efficient algorithms for reachability in directed geometric graphs
• An $$O(n^{\epsilon })$$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
• An O ( n ^ϵ ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

This page was built for publication: \(\tilde{O}(n^{1/3})\)-space algorithm for the grid graph reachability problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115772)