Space complexity of the directed reachability problem over surface-embedded graphs

DOI10.1007/978-3-319-05446-9_3MaRDI QIDQ2821694zbMATH OpenOpenAlexFDO

Authors N. V. Vinodchandran

Publication date 22 September 2016

Published in Perspectives in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-05446-9_3

zbMATH Keywords

computational complexitygraph reachabilityspace-bounded computation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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
• \(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability
• Reachability Problems: An Update
• \(\tilde{O}(n^{1/3})\)-space algorithm for the grid graph reachability problem

Cites work

• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• A very hard log-space counting class
• Directed planar reachability is in unambiguous log-space
• Green's theorem and isolation in planar graphs
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Making Nondeterminism Unambiguous
• Nondeterministic Space is Closed under Complementation
• Relationships between nondeterministic and deterministic tape complexities
• Space Lower Bounds for Maze Threadability on Restricted Machines
• The method of forced enumeration for nondeterministic automata

Cited in

(8)

• On the complexity of directed intersection representation of DAGs
• Space complexity of reachability testing in labelled graphs
• Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
• 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
• Reachability Problems: An Update
• Space Complexity of Reachability Testing in Labelled Graphs
• Space-efficient algorithms for reachability in directed geometric graphs

This page was built for publication: Space complexity of the directed reachability problem over surface-embedded graphs

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