Directed Planar Reachability Is in Unambiguous Log-Space

DOI10.1145/1490270.1490274zbMath1322.68095OpenAlexW2014352902MaRDI QIDQ2947541

Raghunath Tewari, N. V. Vinodchandran, Chris Bourke

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

zbMATH Keywords

planar graphsdirected graph reachabilityunambiguous log-space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Connectivity (05C40)

Related Items (20)

Depth-first search in directed planar graphs, revisited ⋮ On the power of unambiguity in log-space ⋮ Unnamed Item ⋮ Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata ⋮ Space complexity of perfect matching in bounded genus bipartite graphs ⋮ The isomorphism problem for planar 3-connected graphs is in unambiguous logspace ⋮ Deterministically isolating a perfect matching in bipartite planar graphs ⋮ Planarity Testing Revisited ⋮ Space Complexity of Reachability Testing in Labelled Graphs ⋮ String shuffle: circuits and graphs ⋮ Green's theorem and isolation in planar graphs ⋮ Planar and grid graph reachability problems ⋮ Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs ⋮ \textsc{ReachFewL} = \textsc{ReachUL} ⋮ Unnamed Item ⋮ Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs ⋮ Compressed Decision Problems in Hyperbolic Groups. ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ Space complexity of reachability testing in labelled graphs ⋮ Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

This page was built for publication: Directed Planar Reachability Is in Unambiguous Log-Space