Directed planar reachability is in unambiguous log-space
DOI10.1145/1490270.1490274zbMATH Open1322.68095OpenAlexW2014352902MaRDI QIDQ2947541FDOQ2947541
Authors: Chris Bourke, Raghunath Tewari, N. V. Vinodchandran 
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/1490270.1490274
Recommendations
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- On the power of unambiguity in log-space
- Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
- Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
- Reachability in \(K_{3,3}\)-free and \(K_5\)-free graphs is in unambiguous logspace
Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (31)
- Planar and grid graph reachability problems
- Reachability in \(K_{3,3}\)-free and \(K_5\)-free graphs is in unambiguous logspace
- Depth-first search in directed planar graphs, revisited
- Space complexity of the directed reachability problem over surface-embedded graphs
- Longest paths in planar DAGs in unambiguous log-space
- String shuffle: circuits and graphs
- Deterministically isolating a perfect matching in bipartite planar graphs
- Polynomial min/max-weighted reachability is in unambiguous log-space
- Min/max-poly weighting schemes and the NL versus UL problem
- Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata
- Space complexity of perfect matching in bounded genus bipartite graphs
- Derandomizing isolation in space-bounded settings
- Space Complexity of Reachability Testing in Labelled Graphs
- Green's theorem and isolation in planar graphs
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- On the complexity of L-reachability
- On the complexity of L-reachability
- \textsc{ReachFewL} = \textsc{ReachUL}
- A Formalised Lower Bound on Undirected Graph Reachability
- The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
- Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
- Isolating a vertex via lattices: polytopes with totally unimodular faces
- On the power of unambiguity in log-space
- Isolating a vertex via lattices: polytopes with totally unimodular faces
- Compressed Decision Problems in Hyperbolic Groups.
- Space complexity of reachability testing in labelled graphs
- \(\tilde{O}(n^{1/3})\)-space algorithm for the grid graph reachability problem
- ReachFewL = ReachUL
- Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
- Planarity testing revisited
- Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
This page was built for publication: Directed planar reachability is in unambiguous log-space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947541)
