Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
DOI10.1145/1714450.1714451zbMATH Open1322.68107OpenAlexW1988076846MaRDI QIDQ2947545FDOQ2947545
Authors: Jan Kynčl, Tomáš Vyskočil 
Publication date: 24 September 2015
Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1714450.1714451
Recommendations
- Compressed Decision Problems in Hyperbolic Groups.
- scientific article; zbMATH DE number 4001498
- Embedding and canonizing graphs of bounded genus in logspace
- Directed planar reachability is in unambiguous log-space
- Publication:4732110
- 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
- New time-space upperbounds for directed reachability in high-genus and \(H\)-minor-free graphs
- Space complexity of the directed reachability problem over surface-embedded graphs
Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40)
Cited In (11)
- Planar and grid graph reachability problems
- Reachability Problems: An Update
- Reachability in \(K_{3,3}\)-free and \(K_5\)-free graphs is in unambiguous logspace
- New time-space upperbounds for directed reachability in high-genus and \(H\)-minor-free graphs
- Space complexity of perfect matching in bounded genus bipartite graphs
- Derandomizing isolation in space-bounded settings
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Title not available (Why is that?)
- Directed planar reachability is in unambiguous log-space
- On the power of unambiguity in log-space
- Compressed Decision Problems in Hyperbolic Groups.
This page was built for publication: Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947545)
