O(n^1/3)-space algorithm for the grid graph reachability problem
From MaRDI portal
Publication:5115772
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
Cites work
- A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
- Directed planar reachability is in unambiguous log-space
- Planar and grid graph reachability problems
- The complexity of graph connectivity
- Undirected connectivity in log-space
- Universality considerations in VLSI circuits
- \(\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
- scientific article; zbMATH DE number 7650316 (Why is no real title available?)
- An $$O(n^{\epsilon })$$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
- Space-efficient algorithms for reachability in directed geometric 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)
