Directed planar reachability is in unambiguous log-space

DOI10.1145/1490270.1490274MaRDI QIDQ2947541zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

planar graphsdirected graph reachabilityunambiguous log-space

Mathematics Subject Classification ID

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)

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

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
• String shuffle: circuits and graphs
• Longest paths in planar DAGs in unambiguous log-space
• Deterministically isolating a perfect matching in bipartite planar graphs
• Space complexity of perfect matching in bounded genus bipartite 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
• Green's theorem and isolation in planar graphs
• Derandomizing isolation in space-bounded settings
• Space Complexity of Reachability Testing in Labelled 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}
• The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
• A Formalised Lower Bound on Undirected Graph Reachability
• 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)