scientific article; zbMATH DE number 7650316

DOI10.4230/LIPICS.FSTTCS.2019.19MaRDI QIDQ5875652zbMATH OpenFDO

Authors Rahul Jain, Raghunath Tewari

Publication date 3 February 2023

zbMATH Keywords

graph algorithmgrid graphgraph reachabilitysublinear space algorithm

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Recommendations

• \(\tilde{O}(n^{1/3})\)-space algorithm for the grid graph reachability problem
• \(\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
• scientific article; zbMATH DE number 7754308
• Planar and grid graph reachability problems
• Space-efficient algorithms for reachability in directed geometric graphs
• Almost polynomial hardness of node-disjoint paths in grids
• Almost polynomial hardness of node-disjoint paths in grids
• A Formalised Lower Bound on Undirected Graph Reachability

Cited in

(3)

• 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:

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