O(n)-space and polynomial-time algorithm for planar directed graph reachability

DOI10.1007/978-3-662-44465-8_5MaRDI QIDQ2922595zbMATH OpenOpenAlexFDO

Authors Kotaro Nakagawa, Tetsuo Asano, David Kirkpatrick, Osamu Watanabe

Publication date 14 October 2014

Published in Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-44465-8_5

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) 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^{\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
• \(\tilde{O}(n^{1/3})\)-space algorithm for the grid graph reachability problem
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science

Cited in

(22)

• Frameworks for designing in-place graph algorithms
• Space efficient linear time algorithms for BFS, DFS and applications
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• Sublinear-space approximation algorithms for Max r-SAT
• Improved space efficient algorithms for BFS, DFS and applications
• Space complexity of the directed reachability problem over surface-embedded graphs
• Depth-First Search Using O(n) Bits
• 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
• An $$O(n^{\epsilon })$$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• Reachability in a planar subdivision with direction constraints
• Space complexity: what makes planar graphs special?
• An O ( n ^ϵ ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
• A framework for in-place graph algorithms
• \(\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?)
• Space-efficient algorithms for reachability in directed geometric graphs
• Space-efficient algorithms for reachability in directed geometric graphs
• Space efficient algorithm for solving reachability using tree decomposition and separators
• Sublinear-space lexicographic depth-first search for bounded treewidth graphs and planar graphs

This page was built for publication: \(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability

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