scientific article; zbMATH DE number 7650316

DOI10.4230/LIPICS.FSTTCS.2019.19MaRDI QIDQ5875652FDOQ5875652

Raghunath Tewari, Rahul Jain

Publication date: 3 February 2023

Title of this publication is not available (Why is that?)

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
• scientific article; zbMATH DE number 7413501
• Almost polynomial hardness of node-disjoint paths in grids
• A Formalised Lower Bound on Undirected Graph Reachability

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)

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)