An O(n^{\epsilon }) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

DOI10.1007/978-3-662-48971-0_52MaRDI QIDQ3459899zbMATH OpenOpenAlexFDO

Authors Diptarka Chakraborty, Raghunath Tewari

Publication date 11 January 2016

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-48971-0_52

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An O ( n ^ϵ ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
• \(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability
• scientific article; zbMATH DE number 7650316
• Space complexity of the directed reachability problem over surface-embedded graphs
• Space-efficient algorithms for reachability in directed geometric graphs
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• \(\tilde{O}(n^{1/3})\)-space algorithm for the grid graph reachability problem
• A Formalised Lower Bound on Undirected Graph Reachability
• The complexity of pebbling reachability and solvability in planar and outerplanar graphs
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time

Cited in

(12)

• Space complexity of the directed reachability problem over surface-embedded graphs
• \(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability
• Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
• New time-space upperbounds for directed reachability in high-genus and H-minor-free graphs
• Reachability in a planar subdivision with direction constraints
• An O ( n ^ϵ ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
• \(\tilde{O}(n^{1/3})\)-space algorithm for the grid graph reachability problem
• Simultaneous time-space upper bounds for red-blue path problem in planar DAGs
• scientific article; zbMATH DE number 7650316 (Why is no real title available?)
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Space-efficient algorithms for reachability in directed geometric graphs
• Space-efficient algorithms for reachability in directed geometric graphs

This page was built for publication: An $$O(n^{\epsilon })$$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

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